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.

Sottosuccessioni

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 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 $n$ dove i simboli compaiono solo una volta è semplicemente il numero di sottoinsiemi degli indici dei simboli, ovvero $2^{n}$.

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 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 $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 $n+1$ punti. Per cui esistono ${\tbinom {n+1}{2}}={\tfrac {n(n+1)}{2}}$ sottostringhe non vuote.

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.

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.

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

Bordo

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

Superstringa

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

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su sottostringa