Seminar: Stringmatching (SS1995)

1 Knuth–Morris–Pratt und seine Variationen

M. Crochemore, W. Rytter, Text Algorithms, Oxford University Press, 1994, Kapitel 3, 33–53

A. V. Aho, Algorithms for finding patterns in strings, in: J. van Leeuwen (Ed.), Handbook of TCS, Vol. A, 1990, 255–300 (nur der relevante Teil: 3.3)

2 Boyer–Moore und seine Variationen

M. Crochemore, W. Rytter, Text Algorithms, Oxford University Press, 1994, Kapitel 4.1 und 4.2, 55–62

R.N. Horspool, Practical Fast Searching in Strings, Sodtware—Practice and Experience, Vol. 10, 1980, 501–506

A. V. Aho, Algorithms for finding patterns in strings, in: J. van Leeuwen (Ed.), Handbook of TCS, Vol. A, 1990, 255–300 (nur der relevante Teil: 3.4)

3 Lower Bounds on String Matching

3.1 Literatur

R. L. Rivest, On the worst-case behavior of string-searching algorithms, SIAM Journal on Computing, Vol. 6, No. 4, 1977, 669–674

4 Time-Space Optimal String Matching

M. Crochemore, String Matching on Ordered Alphabets, Theoretical Computer Science, 1992, 33–47

M. Crochemore, W. Rytter, Text Algorithms, Oxford University Press, 1994, Kapitel 13, 289–325

5 Multi Pattern Matching

A. V. Aho, Algorithms for finding patterns in strings, in: J. van Leeuwen (Ed.), Handbook of TCS, Vol. A, 1990, 255–300 (nur der relevante Teil: 4. Matching sets of keywords)

A. V. Aho, M. Corasick, Efficient string matching: An aid to bibliographical search, CACM 18, 1975, 333–340

B. Commentz-Walter, A string matching algorithm fast on the average, in Maurer (Ed.), Automata, Languages and Programming, Lecture Notes in CS, Vol. 71, 1979, 118 – 132

6 Shortest Common Superstring Problem

E. Ukkonen, A linear-time algorithm for finding approximate shortest common superstrings, Algorithmica, Vol. 5, 313–323

S.-H. Teng, F. Yao, Approximating Shortest Superstrings, FOCS 1993, IEEE, 158–165

7 Suffix Trees

M. Crochemore, W. Rytter, Text Algorithms, Oxford University Press, 1994, Kapitel 5.1 – 5.3 und 5.7, 73–87 und 99–104

E. M. McCreight, A space-economical suffix tree construction algorithm, JACM 23, 1976, 262–272

M. T. Chen, J. Seiferas, Efficient and elegant subword tree construction, in: Apostolico, Galil (Ed.) Combinatorical Algorithms on Words, 1985, 97–107

8 Exact Matching in Compressed Files

A. Amir, G. Benson, M. Farach, Let Sleeping Files Lie: Pattern Matching in Z-compressed Files, Symp. on Data Structures and Algorithms, 1994, 705–714

9 Approximate String Matching 1

E. Ukkonen, Algorithms for approximate string matching, Information and Control, Vol. 64, 1985, 100–118

10 Approximate String Matching 2

G. M. Landau, U. Vishkin, Fast string matching with k differences, Journal of Computer and System Sciences, Vol. 37, No. 1, 1988, 63–78

11 Approximate String Matching 3

J. Tarhio, E. Ukkonen, Approximate Boyer–Moore String Matching, SIAM J. on Computing, Vol. 22, No. 2, 1993, 243–260

12 Approximate String Matching 4

W. I. Chang, E. L. Lawler, Approximate string matching in sublinear expected time, Proc. of the 31st IEEE Symp. on Found. of CS, Vol. 1, 1990, 116–124