Themenübersicht 

Exact matching Problem

  1. Boyer-Moore Algorithmus:
  2. Knuth-Morris-Pratt Algorithmus:

Exact set matching Problem:

  1. Aho-Corasick:

Seminumerical matching

  1. Rabin-Karp Algorithmus:
  2. grep:

Suche mit Automaten

  1. String matching mit endlichen Automaten

Schnelle Heuristiken

  1. FASTA
  2. BLAST

Suffix Baum und seine Anwendungen

  1. Einfuehrung Suffixbaum
    Anwendungen (alle aus [Gusfield]):
  1. APL 4: S. 125 Longest common substring
  2. 7.11/APL 11: S. 138ff Maximal repeat
  3. APL 13: S. 149- 155 Suffix Arrays
  4. Ziv-Lempel Kompressionsalgorithm


Literatur:

[Gusfield]: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, D.Gusfield,  Cambridge Press, New York, 1997

[Cormen]: Introduction to Algorithms, T.H. Cormen, C.E. Leiserson, R.L. Rivest, MIT Press, Cambridge, MA, 1990.