Sottostringa

Una sottostringa, sottosequenza, prefisso o suffisso di una stringa è un sottoinsieme di simboli in una stringa, in cui l'ordine degli elementi è preservato. In questo contesto, i termini stringa e sequenza assumono lo stesso significato.

Sottosequenza

Una sottosequenza di una strina ${\displaystyle T=t_{1}t_{2}\dots t_{n}}$  è una stringa ${\displaystyle {\hat {T}}=t_{i_{1}}\dots t_{i_{m}}}$  tale che ${\displaystyle i_{1}<\dots <i_{m}}$ , dove ${\displaystyle m\leq n}$ . La sottosequenza è una generalizzazione del concetto di sottostringa, suffisso e prefisso. Trovare la stringa più lunga uguale a una sottosequenza di due o più stringhe è noto come il problema della sottosequenza comune più lunga.

Esempio: la stringa anna è una sottosequenza della stringa banana:

banana
 || ||
 an na

Sottostringa

Una sottostringa (o fattore) di una stringa ${\displaystyle T=t_{1}\dots t_{n}}$  è una stringa ${\displaystyle {\hat {T}}=t_{1+i}\dots t_{m+i}}$ , dove ${\displaystyle 0\leq i}$  e ${\displaystyle m+i\leq n}$ . Una sottostringa di una stringa è un prefisso di un suffisso della stringa o, in modo equivalente, un suffisso di un prefisso della stringa. Se ${\displaystyle {\hat {T}}}$  è una sottostringa di ${\displaystyle T}$ , essa è anche una sottosequenza, che è un concetto più generale. Dato un pattern ${\displaystyle P}$ , è possibile trovarne le occorrenze in una strina ${\displaystyle T}$  mediante un algoritmo di ricerca su stringhe. Trovare la stringa più lunga uguale a una sottostringa di due o più stringhe è noto come il problema della sottostringa comune più lunga.

Esempio: La stringa ana è una sottostringa (e sottosequenza) di banana in due posizioni differenti:

banana
 |||||
 ana||
   |||
   ana

Nella letteratura matematica, le sottostringhe sono anche chiamate subwords (in America) o fattori (in Europa).

References