Suffixbäume

Exaktes String-Matching ist in vielen Algorithmen der Molekularbiologie ein wichtiges Werkzeug. So wird z.B. in der ersten Phase der oben angesprochenen Datenbanksuchen Stringmatching benutzt, um erste Kandidaten zu finden. Ein String der Länge n kann in einem zweiten String der Länge m in Zeit O(n+m) lokalisiert werden (falls vorhanden). Wir werden nun eine sehr mächtige Datenstruktur kennenlernen, mit welcher man in der Lage ist, neben Stringmatching eine Vielzahl anderer String-Probleme zu lösen. Diese sogenannten Suffix-Bäume  wurden bereits 1973 von Weiner [Wei73] entwickelt und drei Jahre später von McCreight [McC76] platzeffizienter gestaltet. Die Analyse ihrer Laufzeit ist relativ kompliziert, und es dauerte bis 1995, ehe Esko Ukkonen [Ukk95] einen alternativen Algorithmus vorschlug, den wir behandeln werden. Ein sehr aktueller Vergleich dieser drei Methoden kann in [GK97] gefunden werden.