Sottostringa: differenze tra le versioni

Versione delle 04:14, 14 mar 2013

Versione delle 15:31, 19 ago 2013

Riga 3:

== Sottosequenza ==

Una sottosequenza di una 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 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 [[massima sottosequenza comune più lunga]].

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

Riga 13:

== 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: