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 stringa $T = t_1 t_2 \dots t_n$ è una stringa $\hat T = t_{i_1} \dots t_{i_m}$ tale che $i_1 < \dots < i_m$, dove $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 $T = t_1 \dots t_n$ è una stringa $\hat T = t_{1+i} \dots t_{m+i}$, dove $0 \leq i$ e $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 $\hat T$ è una sottostringa di $T$, essa è anche una sottosequenza, che è un concetto più generale. Dato un pattern $P$, è possibile trovarne le occorrenze in una strina $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).

Prefisso

Un prefisso di una stringa $T = t_1 \dots t_n$ è una stringa $\widehat T = t_1 \dots t_{m}$, dove $m \leq n$. Un prefisso proprio di una stringa ha lunghezza inferiore rispetto alla stessa ($0 \leq m < n$) ; alcune definizioni in aggiunta richiedono che un prefisso proprio sia non vuoto ($0 < m < n$). Un prefisso può essere visto come un caso speciale di una sottostringa.

Esempio: La stringa ban è un prefisso (e sottostringa e sottosequenza) della stringa banana:

banana
|||
ban

Il simbolo di sottoinsieme quadrato è a volte utilizzato per indicare un prefisso, così $\widehat T \sqsubseteq T$ denota che $\widehat T$ è un prefisso di $T$, definendo una relazione binaria su stringhe, chiamata la relazione prefisso.

Suffisso

Un suffisso di una stringa $T = t_1 \dots t_n$ è una stringa $\hat T = t_{n-m+1} \dots t_{n}$, dove $m \leq n$. Un suffisso proprio di una stringa è di lunghezza inferiore alla stessa ($0 < m \leq n$); di nuovo, un'interpretazione più restrittiva impone che il suffisso proprio sia non vuoto ($0 < m < n$). Un suffisso può essere visto come un caso speciale di una sottostringa.

Esempio: La stringa nana è un suffisso (e una sottostrina e sottosequenza) della stringa banana:

banana
  ||||
  nana