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 è una stringa
tale che
, dove
. 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 dove i simboli compaiono solo una volta è semplicemente il numero di sottoinsiemi degli indici dei simboli, ovvero
.
Sottostringa
Una sottostringa (o fattore) di una stringa è una stringa
, dove
e
. Una sottostringa di una stringa è un prefisso di un suffisso della stringa o, in modo equivalente, un suffisso di un prefisso della stringa. Se
è una sottostringa di
, essa è anche una sottosequenza, che è un concetto più generale. Dato un pattern
, è possibile trovarne le occorrenze in una strina
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 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
punti. Per cui esistono
sottostringhe non vuote.
Prefisso
Un prefisso di una stringa è una stringa
, dove
. Un prefisso proprio di una stringa ha lunghezza inferiore rispetto alla stessa (
) [1]; alcune definizioni[2] in aggiunta richiedono che un prefisso proprio sia non vuoto (
). 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ì denota che
è un prefisso di
, 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 è una stringa
, dove
. Un suffisso proprio di una stringa è di lunghezza inferiore alla stessa (
); di nuovo, un'interpretazione più restrittiva impone che il suffisso proprio sia non vuoto [2] (
). 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 stringhe
, una superstringa dell'insieme
è una singola stringa che contiene tutti gli elementi di
come sottostringhe.Per esempio, una concatenazione degli elementi di
in un ordine qualsiasi produce una superstringa banale di
. Per un esempio più interessante, sia
. Si ha che
è una superstringa di
, ma
è una superstringa più corta.
Note
Altri progetti
Wikimedia Commons contiene immagini o altri file su sottostringa