Sottostringa: differenze tra le versioni

Versione delle 12:42, 19 set 2010

Versione attuale delle 23:30, 18 apr 2024

(10 versioni intermedie di 6 utenti non mostrate)

Riga 1:

Una '''sottostringa''', '''sottosequenza''', '''prefisso''' o '''suffisso''' di una [[Stringa (linguaggi formali)|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.

== SottosequenzaSottosuccessioni ==

{{vedi anche|Sottosuccessione}}

Una sottosequenza di una strina stringa <math>T = t_1 t_2 \dots t_n</math> è una stringa <math>\hat T = t_{i_1} \dots t_{i_m}</math> tale che <math>i_1 < \dots < i_m</math>, dove <math>m \leq n</math>. La sottosequenzasottosuccessione è 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 più lunga]].

Esempio: la stringa <code>anna</code> è una sottosequenza della stringa <code>banana</code>:

Riga 10:

|| ||

an na

Contando la sottosequenza vuota, il numero di sottosequenze di una stringa lunga <math>n</math> dove i simboli compaiono solo una volta è semplicemente il numero di sottoinsiemi degli indici dei simboli, ovvero <math>2^n</math>.

== Sottostringa ==

Una sottostringa (o fattore) di una stringa <math>T = t_1 \dots t_n</math> è una stringa <math>\hat T = t_{1+i} \dots t_{m+i}</math>, dove <math>0 \leq i</math> e <math>m + i \leq n</math>. Una sottostringa di una stringa è un prefisso di un suffisso della stringa o, in modo equivalente, un suffisso di un prefisso della stringa. Se <math>\hat T</math> è una sottostringa di <math>T</math>, essa è anche una sottosequenza, che è un concetto più generale. Dato un pattern <math>P</math>, è possibile trovarne le occorrenze in una strina <math>T</math> mediante un [[algoritmo di ricercapattern 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 più lunga]].

Esempio: La stringa <code>ana</code> è una sottostringa (e sottosequenza) di <code>banana</code> in due posizioni differenti:

Riga 24 ⟶ 26:

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

== Prefisso ==

Un prefisso di una stringa <math>T = t_1 \dots t_n</math> è una stringa <math>\widehat T = t_1 \dots t_{m}</math>, dove <math>m \leq n</math>. Un ''prefisso proprio'' di una stringa ha lunghezza inferiore rispetto alla stessa (<math>0 \leq m < n</math>) <ref name=Kel95>{{en}} Gusfield, Dan (1999). Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press.</ref>; alcune definizioni<ref name="Gus97">{{en}} Kelley, Dean (1995). Automata and Formal Languages: An Introduction. London: Prentice-Hall International. ISBN 0-13-497777-7.</ref> in aggiunta richiedono che un prefisso proprio sia non vuoto (<math>0 < m < n</math>). Un prefisso può essere visto come un caso speciale di una sottostringa.

Esempio: La stringa <code>ban</code> è un prefisso (e sottostringa e sottosequenza) della stringa <code>banana</code>:

Riga 36 ⟶ 40:

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

Nella [[Linguaggio formale|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 ==

Riga 41 ⟶ 47:

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

Esempio: La stringa <code>nana</code> è un suffisso (e una sottostrinasottostringa e sottosequenza) della stringa <code>banana</code>:

banana

Riga 47 ⟶ 53:

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.

== Riferimenti bibliografici ==

== 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 <math>k</math> stringhe <math>P = \{s_1,s_2,s_3,\dots s_k\}</math>, una '''superstringa''' dell'insieme <math>P</math> è una singola stringa che contiene tutti gli elementi di <math>P</math> come sottostringhe.

Per esempio, una concatenazione degli elementi di <math>P</math> in un ordine qualsiasi produce una superstringa banale di <math>P</math>. Per un esempio più interessante, sia <math>P = \{\text{abcc}, \text{efab}, \text{bccla}\}</math>. Si ha che <math>\text{bcclabccefab}</math> è una superstringa di <math>P</math>, ma <math>\text{efabccla}</math> è una superstringa più corta.

== Note ==

<references />

== Altri progetti ==

[[Categoria:Stringhe]]

{{interprogetto}}

[[enCategoria:SubstringStringhe]]

{{Portale|informatica}}

[[pl:Podsłowo]]

[[ru:Подстрока]]

[[uk:Підрядок]]