Zeichenkettenalgorithmus

Zeichenkettenalgorithmen (englisch: string algorithms) sind Verfahren der Informatik zur algorithmischen Bearbeitung endlicher Symbolsequenzen über einem gegebenen Alphabet. Sie umfassen Methoden zur Lokalisation von Teilsequenzen, zur Generierung komprimierter Indizes sowie zur Transformation und Analyse digitaler Texte. Ihre Anwendung erstreckt sich auf Bereiche wie die Bioinformatik, Datenkompression, Plagiaterkennung und das Information Retrieval.

Grundbegriffe

Alphabet

Ein Alphabet ist eine endliche Menge von Symbolen.^[1] Die Symbole eines Alphabets werden auch als Zeichen (englisch: characters) bezeichnet.^[2] Häufig verwendete Alphabete umfassen das binäre Alphabet ${\textstyle \sum =\{0,1\}}$ , das ASCII-Alphabet mit 128 Zeichen oder das Unicode-Alphabet mit über 100.000 Zeichen.^[1]

Zeichenkette

Eine Zeichenkette (englisch: string) ist eine endliche Sequenz von Symbolen über einem Alphabet.^[1] Eine Zeichenkette ${\textstyle w}$ wird typischerweise als ${\textstyle w=w_{1}w_{2}\dotsc w_{n}}$ geschrieben, wobei jedes ${\textstyle w_{i}}$ ein Symbol aus dem zugrunde liegenden Alphabet ist.^[3] Die Länge einer Zeichenkette ist definiert als die Anzahl der Symbole in dieser Sequenz und wird mit ${\textstyle |w|}$ notiert.^[1]

Teilzeichenkette, Präfix und Suffix

Eine Teilzeichenkette (englisch: substring) ist eine zusammenhängende Teilfolge von Zeichen innerhalb einer Zeichenkette.^[4] Ein Präfix ist eine Teilzeichenkette, die am Anfang einer Zeichenkette beginnt, also bei Index 0 startet.^[5] Ein Suffix ist eine Teilzeichenkette, die am Ende einer Zeichenkette endet.^[6] Formal gilt: Ein String ${\textstyle u}$ ist ein Präfix von ${\textstyle w}$ , wenn ein String ${\textstyle v}$ existiert, sodass ${\textstyle w=uv}$ gilt. Entsprechend ist ${\textstyle u}$ ein Suffix von ${\textstyle w}$ , wenn ein String ${\textstyle v}$ existiert, sodass ${\textstyle w=vu}$ gilt.^[4]

Konkatenation

Die Konkatenation ist die Verkettung zweier Zeichenketten, bei der die zweite Zeichenkette an das Ende der ersten angefügt wird. Für zwei Zeichenketten ${\textstyle x}$ und ${\textstyle y}$ wird ihre Konkatenation als ${\textstyle xy}$ notiert. Die Länge der konkatenierten Zeichenkette entspricht der Summe der Längen der beiden Ausgangszeichenketten: ${\textstyle |xy|=|x|+|y|}$ .^[1]

Historische Entwicklung

Die systematische Erforschung von Zeichenkettenalgorithmen begann in den späten 1960er Jahren mit der Veröffentlichung des ersten Bandes von The Art of Computer Programming durch Donald E. Knuth im Jahr 1968. Dieses Werk legte die theoretischen Grundlagen für die Analyse von Algorithmen und etablierte den Begriff der asymptotischen Komplexität in der Informatik.^[7]^[8]

Im Jahr 1970 veröffentlichten James H. Morris jr. und Vaughan R. Pratt einen Technical Report, der die Grundlage für den später nach ihnen und Knuth benannten Algorithmus legte.^[9]^[10] Die endgültige Version des Knuth-Morris-Pratt-Algorithmus erschien 1977 in der Fachzeitschrift SIAM Journal on Computing und stellte den ersten linearen String-Matching-Algorithmus dar.^[11]^[12]

Im selben Jahr 1977 wurde der Boyer-Moore-Algorithmus von Robert S. Boyer und J Strother Moore vorgestellt, der durch seine rückwärts gerichtete Suche und seine Verschiebungsheuristiken eine deutliche Beschleunigung in der Praxis ermöglichte.^[13]^[14]

Der Rabin-Karp-Algorithmus, der auf dem Prinzip des Fingerprinting basiert, wurde 1980 entwickelt und nutzt Rolling-Hash-Funktionen für effiziente Mustersuche.^[15]

Ein bedeutender Meilenstein in der Entwicklung von Datenstrukturen für Zeichenketten war die Einführung der Suffixarrays durch Udi Manber und Eugene Myers im Jahr 1993. Diese Datenstruktur bot eine platzsparende Alternative zu Suffixbäumen.^[16]^[17]

Die erste lineare Konstruktion von Suffixarrays wurde erst im Jahr 2003 erreicht, als mehrere Forschergruppen unabhängig voneinander lineare Algorithmen entwickelten.^[18]

Algorithmen für das String-Matching

Das String-Matching-Problem, auch als Mustersuche (englisch: pattern matching) bezeichnet, besteht darin, alle Vorkommen eines Musters ${\textstyle P}$ in einem Text ${\textstyle T}$ zu finden.^[4] Die Länge des Textes wird typischerweise mit ${\textstyle n}$ und die Länge des Musters mit ${\textstyle m}$ bezeichnet.^[19]

Hauptalgorithmen

Knuth-Morris-Pratt-Algorithmus

Der Knuth-Morris-Pratt-Algorithmus (KMP-Algorithmus) wurde 1977 von Donald E. Knuth, James H. Morris und Vaughan R. Pratt veröffentlicht. Der Algorithmus vergleicht das Muster von links nach rechts mit dem Text. Die zentrale Innovation des KMP-Algorithmus besteht in der Verwendung einer Präfixfunktion (auch Failure-Funktion genannt), die für jede Position im Muster die Länge des längsten echten Präfix angibt, das auch Suffix des aktuellen Präfixes des Musters ist.^[12]

Der KMP-Algorithmus weist eine lineare Zeitkomplexität von ${\textstyle {\mathcal {O}}(m+n)}$ auf.^[12] Bei der Suche werden höchstens ${\textstyle 2n-1}$ Textzeichenvergleiche durchgeführt.^[20] Die Raumkomplexität beträgt ${\textstyle {\mathcal {O}}(m)}$ für die Speicherung der Präfixfunktion.^[12]

Boyer-Moore-Algorithmus

Der Boyer-Moore-Algorithmus, 1977 von Robert S. Boyer und J Strother Moore veröffentlicht, gilt als einer der effizientesten String-Matching-Algorithmen in typischen Anwendungen.^[21] Im Gegensatz zum KMP-Algorithmus vergleicht der Boyer-Moore-Algorithmus das Muster von rechts nach links.^[22]

Der Algorithmus verwendet zwei Verschiebungsfunktionen: die Bad-Character-Heuristik und die Good-Suffix-Heuristik. Die Bad-Character-Heuristik verschiebt das Muster basierend auf dem rechts vom aktuellen Fenster stehenden Zeichen, während die Good-Suffix-Heuristik die Information über übereinstimmende Suffixe nutzt.^[23]

In der Praxis erreicht der Boyer-Moore-Algorithmus oft eine sublineare Laufzeit, da bei großen Alphabeten viele Zeichen des Textes übersprungen werden können. Die Worst-Case-Komplexität beträgt ${\textstyle {\mathcal {O}}(nm)}$ , während die Best-Case-Komplexität ${\textstyle {\mathcal {O}}(n/m)}$ beträgt.^[24] Die Raumkomplexität liegt bei ${\textstyle {\mathcal {O}}(m+|\sum |)}$ , wobei ${\textstyle |\sum |}$ die Größe des Alphabets bezeichnet.

Rabin-Karp-Algorithmus

Der Rabin-Karp-Algorithmus wurde 1987 von Richard M. Karp und Michael O. Rabin entwickelt. Der Algorithmus verwendet das Prinzip des Rolling-Hash für effiziente Mustersuche.^[15] Dabei wird für das Muster und für jedes Fenster der Länge ${\textstyle m}$ im Text ein Hashwert berechnet.^[25] Statt direkter Zeichenvergleiche werden zunächst die Hashwerte verglichen, und nur bei Übereinstimmung erfolgt ein exakter Vergleich.^[26]

Der Rabin-Karp-Algorithmus ist besonders effektiv für die Mehrfachmustersuche, bei der mehrere Muster gleichzeitig gesucht werden.^[26] Die durchschnittliche Zeitkomplexität beträgt ${\textstyle {\mathcal {O}}(n)}$ , während der Worst-Case ${\textstyle {\mathcal {O}}(m\times n)}$ beträgt.^[27] Die Raumkomplexität ist ${\textstyle {\mathcal {O}}(1)}$ , da keine zusätzlichen Datenstrukturen benötigt werden.^[25]

Aho-Corasick-Algorithmus

Der Aho-Corasick-Algorithmus wurde 1975 von Alfred V. Aho und Margaret J. Corasick entwickelt. Er löst das Problem des Mehrfachmuster-Matchings, bei dem mehrere Muster gleichzeitig in einem Text gesucht werden.^[28]

Der Algorithmus basiert auf einem endlichen Automaten, der aus einem Trie der Muster mit zusätzlichen Failure-Links konstruiert wird. Die Zeitkomplexität beträgt ${\textstyle {\mathcal {O}}(n+m+z)}$ , wobei ${\textstyle z}$ die Anzahl der gefundenen Übereinstimmungen ist.^[28] Die Raumkomplexität liegt bei ${\textstyle {\mathcal {O}}(m\times L)}$ , wobei ${\textstyle L}$ die maximale Musterlänge ist.

Anwendungen des Aho-Corasick-Algorithmus umfassen die Tokenisierung von Texten und die Erkennung von Eindringlingen in Netzwerken (Intrusion Detection).^[29]

Weitere String-Matching-Algorithmen

Neben den genannten Hauptalgorithmen existieren zahlreiche weitere Verfahren für das String-Matching:

Der Horspool-Algorithmus (1980) stellt eine vereinfachte Variante des Boyer-Moore-Algorithmus dar, die ausschließlich die Bad-Character-Heuristik verwendet.^[30] Der Sunday-Algorithmus (1990), auch als „Quick-Search“ bekannt, nutzt das Zeichen unmittelbar nach dem aktuellen Suchfenster für die Verschiebungsberechnung.^[31]^[32] Der Zhu-Takaoka-Algorithmus (1987) erweitert die Bad-Character-Heuristik auf zwei Zeichen.^[33] Der Turbo-BM-Algorithmus (1992) führt den Turbo-Shift ein, der den Worst-Case des Boyer-Moore-Algorithmus verbessert.^[19] Der Apostolico-Giancarlo-Algorithmus (1986) bietet eine einfache lineare Schranke für das String-Matching.^[34] Der Two-Way-Algorithmus (1991) arbeitet in-place mit ${\textstyle {\mathcal {O}}(n)}$ -Zeitkomplexität und wird in der GNU-C-Bibliothek (glibc) verwendet.^[35] Der Commentz-Walter-Algorithmus (1979) kombiniert die Strategien von Boyer-Moore und Aho-Corasick für die Mehrfachmustersuche.^[13]^[36] Die Shift-Or- und Shift-And-Algorithmen (1992) nutzen bit-parallele Operationen für das String-Matching.^[37]

Datenstrukturen

Suffixbäume

Ein Suffixbaum ist eine komprimierte Trie-Datenstruktur, die alle Suffixe einer gegebenen Zeichenkette speichert.^[38] Die Entwicklung von Suffixbäumen begann mit Peter Weiner, der 1973 den ersten Linearzeitalgorithmus zur Konstruktion vorstellte.^[39] Der Weiner-Algorithmus hat eine Zeitkomplexität von ${\textstyle {\mathcal {O}}(n)}$ , benötigt jedoch Speicherplatz von ${\textstyle {\mathcal {O}}(n\cdot |\sum |)}$ Speicherplatz.^[40]

Edward McCreight verbesserte 1976 den Algorithmus und reduzierte den Speicherbedarf auf ${\textstyle {\mathcal {O}}(n)}$ .^[40] Der McCreight-Algorithmus ist platzsparender als der Weiner-Algorithmus, arbeitet jedoch offline und benötigt den gesamten Text im Voraus.^[39] Esko Ukkonen entwickelte 1995 einen Online-Algorithmus zur Suffixbaum-Konstruktion mit ${\textstyle {\mathcal {O}}(n)}$ -Speicherbedarf.^[41] Der Ukkonen-Algorithmus baut den Suffixbaum schrittweise auf und kann Zeichen für Zeichen verarbeiten.^[42] Eine umfassende Darstellung von Algorithmen auf Suffixbäumen und verwandten Datenstrukturen bietet das Lehrbuch Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology von Dan Gusfield aus dem Jahr 1997.^[40]

Suffixarrays

Ein Suffixarray ist eine sortierte Liste aller Suffixe einer Zeichenkette, die als Array von Startindizes repräsentiert wird.^[16] Die Einführung von Suffixarrays erfolgte 1993 durch Udi Manber und Eugene Myers.^[17] Der Manber-Myers-Algorithmus zur Konstruktion hat eine Zeitkomplexität von ${\textstyle {\mathcal {O}}(n\log n)}$ , während die Suche nach einem Muster Zeit von ${\textstyle {\mathcal {O}}(m\log n)}$ benötigt.^[16]

Die Entwicklung linearer Konstruktionsalgorithmen für Suffixarrays war ein bedeutender Forschungsschwerpunkt.^[16] Erst 2003 wurden mehrere unabhängige Algorithmen mit linearer Laufzeit vorgestellt.^[18] Ein eleganter Algorithmus zur Konstruktion von Suffixarrays wurde von Rajasekaran und Nicolae 2014 beschrieben.^[43]

Tries und Patricia-Trees

Ein Trie (auch Präfixbaum genannt) ist eine baumbasierte Datenstruktur zur Speicherung von Zeichenketten, bei der jeder Knoten ein Zeichen repräsentiert.^[44] Tries werden für Autocomplete-Funktionen, Rechtschreibprüfungen und IP-Routing eingesetzt.^[45]

Der Patricia-Trie (Practical Algorithm To Retrieve Information Coded In Alphanumeric) wurde 1968 von Donald R. Morrison vorgestellt.^[46] Patricia-Tries sind platzoptimierte Varianten von Tries, die Pfadkomprimierung verwenden und ${\textstyle {\mathcal {O}}(n)}$ -Speicher benötigen.^[47]^[48]

Burrows-Wheeler-Transformation

Die Burrows-Wheeler-Transformation (BWT) wurde 1994 von Michael Burrows und David Wheeler am DEC Systems Research Center (SRC) in Palo Alto entwickelt.^[49] Die BWT ist eine reversible Transformation, die eine Zeichenkette in eine permutierte Form überführt, in der gleiche Zeichen typischerweise gruppiert auftreten.^[50] Diese Eigenschaft macht die BWT besonders geeignet für die Datenkompression.^[51]

Die BWT bildet die Grundlage für viele moderne Kompressionsalgorithmen, darunter bzip2.^[52] Verbesserungen der Burrows-Wheeler-Kompression wurden von verschiedenen Forschern vorgeschlagen.^[49]

FM-Index

Der FM-Index wurde 2000 von Paolo Ferragina und Giovanni Manzini entwickelt. Der FM-Index ist ein komprimierter Volltext-Index, der die Burrows-Wheeler-Transformation mit Rang- und Selektionsoperationen kombiniert. Der Index benötigt etwa 0,5 Bytes pro Zeichen und ermöglicht effiziente Suchoperationen.^[53]

Der FM-Index wird in der Bioinformatik für die Sequenzalignment eingesetzt, insbesondere in Tools wie Bow-Tie und Burrows-Wheeler-Aligner (BWA).^[54]

Komplexitätsanalyse

Zeitkomplexität

Die Zeitkomplexität von String-Matching-Algorithmen beschreibt die Anzahl der benötigten Operationen in Abhängigkeit von der Textlänge ${\textstyle n}$ und der Musterlänge ${\textstyle m}$ .^[19]

Der naive Algorithmus hat eine Best-Case-Komplexität von ${\textstyle {\mathcal {O}}(n)}$ , eine Average-Case-Komplexität von ${\textstyle {\mathcal {O}}(nm)}$ und eine Worst-Case-Komplexität von ${\textstyle {\mathcal {O}}(nm)}$ .^[55] Der Knuth-Morris-Pratt-Algorithmus garantiert eine Zeitkomplexität von ${\textstyle {\mathcal {O}}(n+m)}$ in allen Fällen.^[56] Der Boyer-Moore-Algorithmus erreicht im Best-Case ${\textstyle {\mathcal {O}}(n/m)}$ , im Average-Case ebenfalls ${\textstyle {\mathcal {O}}(n/m)}$ und im Worst-Case ${\textstyle {\mathcal {O}}(nm)}$ .^[57] Der Rabin-Karp-Algorithmus hat eine Best- und Average-Case-Komplexität von ${\textstyle {\mathcal {O}}(n+m)}$ und einen Worst-Case von ${\textstyle {\mathcal {O}}(nm)}$ .^[27] Die Z-Algorithmus bietet eine Zeitkomplexität von ${\textstyle {\mathcal {O}}(n+m)}$ .^[58] Der Aho-Corasick-Algorithmus arbeitet in ${\textstyle {\mathcal {O}}(n+m+z)}$ , wobei ${\textstyle z}$ die Anzahl der Ausgaben ist.^[59]

Raumkomplexität

Die Raumkomplexität beschreibt den zusätzlichen Speicherbedarf neben dem Eingabetext und dem Muster.

Der naive Algorithmus und der Rabin-Karp-Algorithmus benötigen zusätzlichen Speicher von ${\textstyle {\mathcal {O}}(1)}$ .^[60] Der Knuth-Morris-Pratt-Algorithmus benötigt Speicher von ${\textstyle {\mathcal {O}}(m)}$ für die Präfixfunktion.^[61] Der Boyer-Moore-Algorithmus benötigt Speicher von ${\textstyle {\mathcal {O}}(m+|\sum |)}$ für die Verschiebungstabellen.^[57] Der Z-Algorithmus benötigt Speicher von ${\textstyle {\mathcal {O}}(n+m)}$ für das Z-Array.^[58] Der Aho-Corasick-Algorithmus benötigt Speicher von ${\textstyle {\mathcal {O}}(m\times L)}$ für den Automaten.^[62]

Untere Schranken

Ronald L. Rivest bewies 1977, dass für das String-Matching mindestens Zeichenabfragen von ${\textstyle n-|p|+1}$ notwendig sind. Diese untere Schranke gilt für deterministische Algorithmen im Worst-Case.^[63]

Zsolt Tuza zeigte, dass mehr als 50 Prozent aller binären Muster „evasive“ sind, was bedeutet, dass alle Zeichen abgefragt werden müssen.^[64]

Anwendungsgebiete

Bioinformatik

Die Bioinformatik ist eines der wichtigsten Anwendungsgebiete für Zeichenkettenalgorithmen.^[65] Die Analyse biologischer Sequenzen wie DNA, RNA und Proteine erfordert effiziente Algorithmen für das Muster-Matching und das Sequenzalignment.^[66]

Der Needleman-Wunsch-Algorithmus, 1970 entwickelt, löst das Problem des globalen Alignments zweier Sequenzen mit einer Zeitkomplexität von ${\textstyle {\mathcal {O}}(mn)}$ .^[67]^[68] Der Smith-Waterman-Algorithmus, 1981 veröffentlicht, berechnet lokale Alignments zwischen Sequenzen.^[69] Die Burrows-Wheeler-Transformation und der FM-Index bilden die Grundlage für moderne Sequenzierungswerkzeuge wie Bow-Tie und BWA.^[53] Diese Tools ermöglichen die effiziente Kartierung von kurzen DNA-Sequenzen auf Referenzgenome.^[70]

Textverarbeitung

In der Textverarbeitung werden Zeichenkettenalgorithmen für Suchen-und-Ersetzen-Funktionen, reguläre Ausdrücke und Texteditoren eingesetzt.

Der Boyer-Moore-Algorithmus ist etwa drei bis fünf Mal schneller als der Knuth-Morris-Pratt-Algorithmus (KMP) in typischen Anwendungen und wird im GNU-grep-Programm verwendet.^[71] Die Implementierung des KMP-Algorithmus wird in verschiedenen akademischen Kursen behandelt.^[19]

Datenkompression

Die Datenkompression nutzt Zeichenkettenalgorithmen zur Reduktion der Speichergröße von Texten.

Die Burrows-Wheeler-Transformation ist eine Kernkomponente des Kompressionsprogramms bzip2.^[72] Die Lempel-Ziv-Kompressionsalgorithmen (LZ77 und LZ78), 1977 und 1978 entwickelt,^[73] bilden die Grundlage für viele moderne Kompressionsformate wie ZIP und Gzip.^[74]

Information Retrieval

Im Information Retrieval werden Zeichenkettenalgorithmen für die Indexierung und Suche in großen Textsammlungen eingesetzt.^[75]

Suffixarrays und Suffixbäume ermöglichen effiziente Volltextsuchen in großen Dokumentensammlungen.^[17] Tries werden für Autocomplete-Funktionen, Rechtschreibprüfungen und IP-Routing-Tabellen verwendet.^[76] Das approximative String-Matching ermöglicht die Suche nach ähnlichen Zeichenketten und wird für fehlertolerante Suchen eingesetzt.^[77]

Plagiaterkennung

Die Plagiaterkennung nutzt Zeichenkettenalgorithmen zur Identifikation von Textüberlappungen und ähnlichen Dokumenten.

Der Rabin-Karp-Algorithmus mit Rolling-Hash wird für die effiziente Erkennung von Textplagiaten eingesetzt.^[78] Der Winnowing-Algorithmus basiert auf k-gram-Hashes und wird für die Dokumentensignatur verwendet.^[79] String-Ähnlichkeitsmaße wie Tf-idf, Cosine-Similarity, Jaro-Winkler-Distanz und Levenshtein-Distanz werden für die Plagiaterkennung eingesetzt.^[80]

Forensik

Weitere Anwendungen der Zeichenkettenalgorithmen in der Forensik umfassen die Restricted Forensic Levenshtein Distance für die Analyse von DNA-Spuren.^[81]

Einzelnachweise

[1]
John E. Hopcroft et al.: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. 2. überarb. Auflage. Pearson, München 2002, ISBN 978-3-8273-7020-4.
[2]
Christian Wagenknecht, Michael Hielscher: Formale Sprachen, abstrakte Automaten und Compiler: Lehr- und Arbeitsbuch für Grundstudium und Fortbildung. 1. Auflage. Vieweg+Teubner, Wiesbaden 2009, ISBN 978-3-8348-0624-6.
[3]
Models of Computation. Lecture 1: Strings. The Grainger College of Engineering, 2018, abgerufen am 16. Februar 2026.
[4]
Christian Charras, Thierry Lecroq: Handbook of Exact String-Matching Algorithms. London 2004, ISBN 0-9543006-4-5 (univ-mlv.fr [PDF]).
[5]
Marcus Kracht: Formale Methoden. Universität Bielefeld, 2018, abgerufen am 16. Februar 2026.
[6]
Sara Giuliani et al.: When a Dollar Makes a BWT. In: Theoretical Computer Science. Band 857. Amsterdam 2021, S. 123–146, doi:10.1016/j.tcs.2021.01.008.
[7]
History of Algorithmic Analysis. Pomona College, abgerufen am 16. Februar 2026.
[8]
Donald E. Knuth: The Art of Computer Programming. Band 1. Addison-Wesley, Upper Saddle River 1968.
[9]
Cyril Nicaud et al.: Branch Prediction Analysis of Morris-Pratt and Knuth-Morris-Pratt Algorithms. In: Leibniz International Proceedings in Informatics. Band 331. Saarbrücken 2025, S. 8:1–8:17, doi:10.4230/LIPIcs.CPM.2025.8.
[10]
James H. Morris jr., Vaughan R. Pratt: A Linear Pattern-Matching Algorithm. Berkeley 1970.
[11]
Amihood Amir et al.: Dynamic Text and Static Pattern Matching. In: ACM Transactions on Algorithms. Jg. 3, Nr. 2. New York 2007, doi:10.1145/1240233.1240242.
[12]
Donald E. Knuth et al.: Fast Pattern Matching in Strings. In: SIAM Journal on Computing. Jg. 6, Nr. 2. Philadelphia 1977, S. 323–350, doi:10.1137/0206024.
[13]
Sun Wu, Udi Manber: A Fast Algorithm for Multi-Pattern Searching. Tucson 1994 (arizona.edu [PDF]).
[14]
Robert S. Boyer, J Strother Moore: A Fast String Searching Algorithm. In: Communications of the ACM. Jg. 20. New York 1977, S. 762–772.
[15]
Richard M. Karp, Michael O. Rabin: Efficient Randomized Pattern-Matching Algorithms. In: IBM Journal of Research and Development. Jg. 31. New York 1987, S. 249–260, doi:10.1147/rd.312.0249.
[16]
Pang Ko, Srinivas Aluru: Space Efficient Linear Time Construction of Suffix Arrays. In: Journal of Discrete Algorithms. Jg. 3, Nr. 2–4. Amsterdam 2005, S. 143–156, doi:10.1016/j.jda.2004.08.002.
[17]
Udi Manber, Eugene W. Myers: Suffix Arrays: A New Method for On-Line String Searches. In: SIAM Journal on Computing. Jg. 22, Nr. 5. Philadelphia 1993, S. 935–948, doi:10.1137/0222058.
[18]
Juha Kärkkäinen, Peter Sanders: Simple Linear Work Suffix Array Construction. In: Jos C. M. Baeten et al. (Hrsg.): Automata, Languages and Programming. Springer, Berlin 2003, doi:10.1007/3-540-45061-0_73.
[19]
Maxime Crochemore, Thierry Lecroq: Pattern-Matching and Text-Compression Algorithms. In: ACM Computing Surveys. Jg. 28, Nr. 1. New York 1996, S. 39–41, doi:10.1145/234313.234331.
[20]
Dany Breslauer et al.: Tight Comparison Bounds for the String Prefix-Matching Problem. In: Information Processing Letters. Band 47, Nr. 1. Amsterdam 1993, S. 51–57, doi:10.1016/0020-0190(93)90156-4.
[21]
Priya Sharma: Boyer-Moore String Algorithm: How It Works with Examples. ACTE, 22. April 2025, abgerufen am 17. Februar 2026.
[22]
Boyer–Moore Algorithm: Fast String Searching Explained. NxtWave, 7. Januar 2025, abgerufen am 17. Februar 2026.
[23]
Ubaid Ahmed: Boyer Moore Algorithm with Bad character Heuristic. Topcoder, 15. November 2021, abgerufen am 17. Februar 2026.
[24]
Zvi Galil: On Improving the Worst Case Running Time of the BoyerMoore String Matching Algorithm. In: Communications of the ACM. Jg. 22, Nr. 9. New York 1979, S. 505–508, doi:10.1145/359146.359148.
[25]
Robert Glück, Tetsuo Yokoyama: Reversible Programming: A Case Study of Two String-Matching Algorithms. In: Electronic Proceedings in Theoretical Computer Science. Band 373, Nr. 6. Sydney 2022, doi:10.4204/EPTCS.373.1.
[26]
Rabin-Karp Algorithm for Pattern Searching. GeeksforGeeks, 1. August 2025, abgerufen am 17. Februar 2026.
[27]
Rabin-Karp Algorithm. Programiz, Parewa Labs, abgerufen am 17. Februar 2026.
[28]
Alfred V. Aho, Margaret J. Corasick: Efficient String Matching: An Aid to Bibliographic Search. In: Communications of the ACM. Jg. 18, Nr. 6. New York 1975, S. 333–340, doi:10.1145/360825.360855.
[29]
Rushikesh Lakhotiya: Lexical Analyzer. In: International Research Journal of Engineering and Technology. Jg. 10, Nr. 1, 2023, S. 384–388.
[30]
R. Nigel Horspool: Practical Fast Searching in Strings. In: Software: Practice & Experience. Jg. 10, Nr. 6. Chichester 1980, S. 501–506.
[31]
Mosleh M. Abu-Alhaj et al.: An innovative platform to improve the performance of exact-string-matching algorithms. In: International Journal of Computer Science and Information Security. Band 7, Nr. 1, 2010, S. 280–283, doi:10.48550/ARXIV.1002.2222.
[32]
Daniel M. Sunday: A very fast substring search algorithm. In: Communications of the ACM. Jg. 33, Nr. 8. New York 1990, S. 132–142, doi:10.1145/79173.79184.
[33]
Thomas Berry, Somasundaram Ravindran: Tuning the Zhu-Takaoka string matching algorithm and experimental results. In: Kybernetika. Jg. 38, Nr. 1. Prag 2002, S. 67–80.
[34]
Maxime Crochemore: A unifying look at the Apostolico–Giancarlo string-matching algorithm. In: Journal of Discrete Algorithms. Jg. 1, Nr. 1. Amsterdam 2003, S. 37–52, doi:10.1016/S1570-8667(03)00005-4.
[35]
Maxime Crochemore, Dominique Perrin: Two-Way String-Matching. In: Journal of the ACM. Jg. 38, Nr. 3. New York 1991, S. 650–674, doi:10.1145/116825.116845.
[36]
Beate Commentz-Walter: A String Matching Algorithm Fast on the Average. In: Hermann A. Maurer (Hrsg.): Automata, Languages and Programming. Springer, Berlin 1979, S. 118–132, doi:10.1007/3-540-09510-1_10.
[37]
Gonzalo Navarro, Mathieu Raffinot: Fast and Flexible String Matching by Combining Bit-Parallelism and Suffix Automata. In: Journal of Experimental Algorithmics. Jg. 5, Nr. 4. New York 2000, doi:10.1145/351827.384246.
[38]
Sartaj Sahni: Data structures, algorithms, and applications in Java. 2. Auflage. Silicon Press, Summit 2005, ISBN 0-929306-33-3.
[39]
Diptarama Hendrian et al.: Linear Time Online Algorithms for Constructing Linear-size Suffix Trie. In: Theoretical Computer Science. Band 1015, C. Amsterdam 2024, doi:10.1016/j.tcs.2024.114765.
[40]
Dan Gusfield: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge 1997, Kap. 5: Introduction to Suffix Trees, S. 89–93, doi:10.1017/CBO9780511574931.007.
[41]
Esko Ukkonen: On-line construction of suffix trees. In: Algorithmica. Band 14. New York 1995, S. 249–260, doi:10.1007/BF01206331.
[42]
Amarjeet Kumar: Suffix Tree-Ukkonen's Algorithm. Coding Ninjas, 27. März 2024, abgerufen am 17. Februar 2026.
[43]
Sanguthevar Rajasekaran, Marius Nicolae: An elegant algorithm for the construction of suffix arrays. In: Journal of Discrete Algorithms. Band 27. Amsterdam 2014, S. 21–28, doi:10.1016/j.jda.2014.03.001.
[44]
René de la Briandais: File Searching Using Variable Length Keys. In: Proceedings AFIPS Western Joint Computer Conference. Band 15. San Francisco 1959, S. 295–298, doi:10.1145/1457838.1457895.
[45]
Applications, Advantages and Disadvantages of Trie. GeeksforGeeks, 23. Juli 2025, abgerufen am 17. Februar 2026.
[46]
Donald R. Morrison: PATRICIA – Practical Algorithm To Retrieve Information Coded in Alphanumeric. In: Journal of the ACM. Jg. 15, Nr. 4. New York 1968, S. 514–534, doi:10.1145/321479.321481.
[47]
Robert Sedgewick: Algorithms in C. Addison-Wesley, Reading 1990, ISBN 0-201-51425-7.
[48]
Donald E. Knuth: The Art of Computer Programming. 2. Auflage. Addison-Wesley, Reading 1973.
[49]
Peter M. Fenwick: Burrows-Wheeler compression: Principles and reflections. In: Theoretical Computer Science. Band 387, Nr. 3. Amsterdam 2007, S. 200–219, doi:10.1016/j.tcs.2007.07.012.
[50]
Peter M. Fenwick: The Burrows-Wheeler Transform for Block Sorting Text Compression – Principles and Improvements. In: The Computer Journal. Jg. 39, Nr. 9. Oxford 1996, S. 731–740, doi:10.1093/comjnl/39.9.731.
[51]
Shir Landau, Elad Verbin: The Burrows-Wheeler compression algorithm is even better than what you have thought. University of California, Davis, 8. April 2005, abgerufen am 18. Februar 2026.
[52]
History of Lossless Data Compression Algorithms. Engineering and Technology History Wiki (ETHW), 22. Januar 2019, abgerufen am 18. Februar 2026.
[53]
Paolo Ferragina, Giovanni Manzini: The FM-Index: A Compressed Full-Text Index Based on the BWT. DIMACS, abgerufen am 18. Februar 2026.
[54]
bvSFM: a tool for sequence alignment. GAZ – I3A Research Group, abgerufen am 18. Februar 2026.
[55]
Naive algorithm for Pattern Searching. GeeksforGeeks, 20. April 2024, abgerufen am 18. Februar 2026.
[56]
KMP Algorithm for Pattern Searching. GeeksforGeeks, 10. Oktober 2025, abgerufen am 18. Februar 2026.
[57]
Boyer Moore Algorithm for Pattern Searching. GeeksforGeeks, 23. Juli 2025, abgerufen am 18. Februar 2026.
[58]
Z algorithm (Linear time pattern searching Algorithm). GeeksforGeeks, 5. August 2025, abgerufen am 18. Februar 2026.
[59]
Aho-Corasick algorithm. Rosetta Code, 6. Februar 2026, abgerufen am 18. Februar 2026.
[60]
Akhtar Rasool et al.: String Matching Methodologies: A Comparative Analysis. In: International Journal of Computer Science and Information Technologies. Jg. 3, Nr. 2, 2012, S. 3394–3397 (ijcsit.com [PDF]).
[61]
Roman Vashchegin: Conquer String Search with the Aho-Corasick Algorithm. Toptal, 25. Oktober 2023, abgerufen am 18. Februar 2026.
[62]
Aho-Corasick Algorithm for Pattern Searching. GeeksforGeeks, 23. Juli 2025, abgerufen am 18. Februar 2026.
[63]
Ronald L. Rivest: On the Worst-Case Behavior of String-Searching Algorithms. In: SIAM Journal on Computing. Jg. 6, Nr. 4. Philadelphia 1977, S. 669–674, doi:10.1137/0206048.
[64]
Xiaoyu He et al.: On the Decision Tree Complexity of String Matching. DROPS, Schloss Dagstuhl – LZI, 2012, abgerufen am 18. Februar 2026.
[65]
Ahmad Retha: Practical algorithms for biological sequence analysis: methods and applications. King’s College London, 2019, abgerufen am 18. Februar 2026.
[66]
José Eduardo Kroll et al.: A tool for integrating genetic and mass spectrometry‐based peptide data: Proteogenomics Viewer: PV: A genome browser‐like tool, which includes MS data visualization and peptide identification parameters. In: Bioessays. Jg. 39, Nr. 7. Hoboken 2017, doi:10.1002/bies.201700015.
[67]
Alexander Chan: An Analysis of Pairwise Sequence Alignment Algorithm Complexities: Needleman-Wunsch, Smith-Waterman, FASTA, BLAST and Gapped BLAST. Doug Brutlag, abgerufen am 18. Februar 2026.
[68]
Saul B. Needleman, Christian D. Wunsch: A general method applicable to the search for similarities in the amino acid sequence of two proteins. In: Journal of Molecular Biology. Band 48, Nr. 3. Amsterdam 1970, S. 443–453, doi:10.1016/0022-2836(70)90057-4.
[69]
Temple F. Smith, Michael S. Waterman: Identification of common molecular subsequences. In: Journal of Molecular Biology. Band 147. Amsterdam 1981, S. 195–197, doi:10.1016/0022-2836(81)90087-5.
[70]
Ben Langmead et al.: Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. In: Genome Biology. Jg. 10, Nr. 3. London 2009, doi:10.1186/gb-2009-10-3-r25.
[71]
Sarhan S. Darwood, Saman A. Barakat: Empirical Performance Evaluation of Knuth Morris Pratt And Boyer Moore String Matching Algorithms. In: Journal of Duhok University. Band 23, Nr. 1, 2020, S. 134–143, doi:10.26682/sjuod.2020.23.1.14.
[72]
Mark Nelson: Data Compression with the Burrows-Wheeler Transform. In: Dr. Dobb’s Journal. San Francisco 1996 (digiater.nl).
[73]
Milestones: Lempel-Ziv Data Compression Algorithm, 1977. Engineering and Technology History Wiki (ETHW), 31. Oktober 2024, abgerufen am 18. Februar 2026.
[74]
GNU Gzip: General file (de)compression. GNU, Free Software Foundation, abgerufen am 18. Februar 2026.
[75]
Ricardo Baeza-Yates et al.: Searching large text collections. In: James Abello, Panos M. Pardalos (Hrsg.): Handbook of massive data sets. Kluwer, Dordrecht 2002, ISBN 978-1-4020-0489-6, S. 195–243, doi:10.5555/779232.779240.
[76]
Anish Kumar: Trie in Javascript: the Data Structure behind Autocomplete. StackFull.dev, 24. April 2025, abgerufen am 18. Februar 2026.
[77]
Gonzalo Navarro: A Guided Tour to Approximate String Matching. In: ACM Computing Surveys. Jg. 33, Nr. 1. New York 2001, S. 31–88, doi:10.1145/375360.375365.
[78]
Ruth Rani Simanjuntak et al.: Application of the KARP RABIN Algorithm for Plagiarism Detection System in Thesis Proposal Submission in the Department of Informatics Engineering STMIK Kaputama. In: Journal of Artificial Intelligence and Engineering Applications. Band 4, Nr. 1, 2024, S. 396–403, doi:10.59934/jaiea.v4i1.644.
[79]
Fingerprinting (hash-based methods) for plagiarism detection. PlagPointer Plagiarismchecker.net, 12. Juli 2025, abgerufen am 18. Februar 2026.
[80]
Fahrudin Mukti Wibowo et al.: Lightweight String Similarity Approaches for Duplicate Detection in Academic Titles. In: Journal of Informatics and Web Engineering. Band 4, Nr. 3, 2025, S. 416–426, doi:10.33093/jiwe.2025.4.3.25.
[81]
Taylor Petty et al.: A New String Edit Distance and Applications. In: Algorithms. Jg. 15, Nr. 7. Basel 2022, doi:10.3390/a15070242.