Sottostringa: differenze tra le versioni

Versione delle 16:28, 19 ago 2013

Versione delle 20:49, 7 ott 2013

Riga 1:

Una '''sottostringa''', '''sottosequenza''', '''prefisso''' o '''suffisso''' di una [[stringa (formale)|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 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]].

:''Articolo principale [[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]].

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