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).

Prefisso

Un prefisso di una stringa ${\displaystyle T=t_{1}\dots t_{n}}$  è una stringa ${\displaystyle {\widehat {T}}=t_{1}\dots t_{m}}$ , dove ${\displaystyle m\leq n}$ . Un prefisso proprio di una stringa ha lunghezza inferiore rispetto alla stessa (${\displaystyle 0\leq m<n}$ ) ^[1]; alcune definizioni^[2] in aggiunta richiedono che un prefisso proprio sia non vuoto (${\displaystyle 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ì ${\displaystyle {\widehat {T}}\sqsubseteq T}$  denota che ${\displaystyle {\widehat {T}}}$  è un prefisso di ${\displaystyle T}$ , definendo una relazione binaria su stringhe, chiamata la relazione prefisso.

Suffisso

Un suffisso di una stringa ${\displaystyle T=t_{1}\dots t_{n}}$  è una stringa ${\displaystyle {\hat {T}}=t_{n-m+1}\dots t_{n}}$ , dove ${\displaystyle m\leq n}$ . Un suffisso proprio di una stringa è di lunghezza inferiore alla stessa (${\displaystyle 0<m\leq n}$ ); di nuovo, un'interpretazione più restrittiva impone che il suffisso proprio sia non vuoto ^[2] (${\displaystyle 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

Riferimenti bibliografici

1. ^ (EN) Gusfield, Dan (1999). Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press.
2. (EN) Kelley, Dean (1995). Automata and Formal Languages: An Introduction. London: Prentice-Hall International. ISBN 0-13-497777-7.