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.

Lo stesso argomento in dettaglio: Sottosuccessione.

Una sottosequenza di una stringa ${\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 sottosuccessione è 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 massima sottosequenza comune.

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

banana
 || ||
 an na

Contando la sottosequenza vuota, il numero di sottosequenze di una stringa lunga ${\displaystyle n}$ dove i simboli compaiono solo una volta è semplicemente il numero di sottoinsiemi degli indici dei simboli, ovvero ${\displaystyle 2^{n}}$.

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 pattern matching su stringhe. Trovare la stringa più lunga uguale a una sottostringa di due o più stringhe è noto come il problema della massima sottostringa comune.

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

Non contando la sottostringa vuota, il numero di sottostringhe di una stringa lunga ${\displaystyle n}$ dove i simboli compaiono solo una volta è uguale al numero di modi in cui si possono scegliere due "punti" distinti, ognuno posto tra due simboli adiacenti, per marcare rispettivamente l'inizio e la fine della sottostringa. Includendo il punto che precede il primo carattere della stringa e quello che segue l'ultimo, ci sono un totale di ${\displaystyle n+1}$ punti. Per cui esistono ${\displaystyle {\tbinom {n+1}{2}}={\tfrac {n(n+1)}{2}}}$ sottostringhe non vuote.

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.

Nella teoria dei linguaggi formali il termine prefisso di una stringa viene inteso comunemente anche come l'insieme di tutti i prefissi di una stringa rispetto a quel linguaggio.

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 sottostringa e sottosequenza) della stringa banana:

banana
  ||||
  nana

Un albero dei suffissi di una stringa è una struttura dati trie-like che rappresenta tutti i suoi suffissi. Gli alberi dei suffissi hanno un gran numero di applicazioni negli algoritmi su stringhe. L'array dei suffissi è una versione semplificata di questa struttura dati che elenca le posizioni di partenza dei suffissi in ordine alfabetico; condivide molte delle stesse applicazioni.

Una sottostringa si dice bordo quando è contemporaneamente suffisso e prefisso della stessa stringa, ad esempio "bab" è un bordo di "babab".

Dato un insieme di ${\displaystyle k}$ stringhe ${\displaystyle P=\{s_{1},s_{2},s_{3},\dots s_{k}\}}$, una superstringa dell'insieme ${\displaystyle P}$ è una singola stringa che contiene tutti gli elementi di ${\displaystyle P}$ come sottostringhe. Per esempio, una concatenazione degli elementi di ${\displaystyle P}$ in un ordine qualsiasi produce una superstringa banale di ${\displaystyle P}$. Per un esempio più interessante, sia ${\displaystyle P=\{{\text{abcc}},{\text{efab}},{\text{bccla}}\}}$. Si ha che ${\displaystyle {\text{bcclabccefab}}}$ è una superstringa di ${\displaystyle P}$, ma ${\displaystyle {\text{efabccla}}}$ è una superstringa più corta.

• Wikimedia Commons contiene immagini o altri file su sottostringa

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica