Construction of Fundamental Data Structures for Strings

54.95 CHF

Versandkostenfrei

Versandkostenfreie Lieferung!

Lieferzeit: 7-14 Werktage

Artikel-Nr.: 10423349

Beschreibung

· Part I Introduction and Preliminaries

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2 Suffix sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3 Overview of the Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1 Definitions and Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.1 Alphabets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.2 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.3 Model of Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Data Structures for Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.1 Suffix Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.2 LCP Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.3 Lyndon Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.4 Document Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Induced Suffix Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2 A brief history . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3 Induced suffix sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.1 SA in linear time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.2 SA in optimal time/space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

· Part II Augmented Suffix Sorting

4 Inducing the LCP Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2 Inducing the LCP array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2.1 LCP array in linear time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2.2 LCP array in optimal time/space . . . . . . . . . . . . . . . . . . . . . . . .

4.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 Inducing the Document Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.2 Suffix Sorting for String Collections . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.2.1 Inducing SA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.2.2 Inducing SA and DA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.3.1 Computing SA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.3.2 Computing SA and DA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 Inducing the Lyndon Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.2 Inducing the Lyndon array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.2.1 LA in linear time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.2.2 LA in optimal time/space . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

· Part III Conclusions

7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7.1 Contributions and Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Eigenschaften

Breite:	156
Gewicht:	198 g
Höhe:	8
Länge:	235
Seiten:	104
Sprachen:	Englisch
Autor:	Felipe A. Louza, Guilherme P. Telles, Simon Gog

Bewertung

Menü schließen

Bewertungen werden nach Überprüfung freigeschaltet.

Die mit einem * markierten Felder sind Pflichtfelder.

Ich habe die Datenschutzbestimmungen zur Kenntnis genommen.