Sottostringa: differenze tra le versioni

Versione delle 08:14, 18 set 2010

Versione delle 08:18, 18 set 2010

Riga 27:

== 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>Gusfield, Dan (1999). Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press.</ref>; alcune definizioni<ref name=Gus97>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 37:

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]].

== ReferencesBibliografia ==

<references />

{{Reflist|refs=

<ref name=Gus97>{{cite book

| last = Gusfield

| first = Dan

| origyear = 1997

| year = 1999

| title = Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology

| publisher = Cambridge University Press

| ___location = USA

| isbn = 0-521-58519-8

}}</ref>

<ref name=Kel95>{{cite book

| last = Kelley

| first = Dean

| year = 1995

| title = Automata and Formal Languages: An Introduction

| publisher = Prentice-Hall International

| ___location = London

| isbn = 0-13-497777-7

}}</ref>

}}

[[Categoria:Stringhe]]