Sottostringa: differenze tra le versioni

Versione delle 12:42, 19 set 2010

Versione delle 22:23, 6 dic 2010

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.

== Sottosequenza ==

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

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