Sottostringa: differenze tra le versioni

Versione delle 20:49, 7 ott 2013

Versione attuale delle 23:30, 18 apr 2024

(3 versioni intermedie di un altro utente non mostrate)

Riga 1:

Una '''sottostringa''', '''sottosequenza''', '''prefisso''' o '''suffisso''' di una [[stringaStringa (formalelinguaggi 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.

== Sottosuccessioni ==

Riga 31:

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

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 (matematica) | 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 64:

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

== Riferimenti bibliografici ==

<references />

== Altri progetti ==

{{interprogetto}}

[[Categoria:Stringhe]]

{{Portale|informatica}}