String Algorithms
String algorithms process sequences of symbols — text, DNA, or other linear data — to find patterns, index large texts for fast search, and align sequences by similarity.
Definition
String algorithms are procedures and data structures that operate on strings — finite sequences of characters drawn from an alphabet — to solve problems such as locating patterns, indexing for fast lookup, and measuring or aligning similarity between sequences.
Scope
This area covers algorithms and data structures specialized for strings: exact and approximate pattern matching, index structures (tries, suffix trees and arrays) that preprocess text for repeated queries, and sequence-alignment methods for comparing strings. It connects to dynamic programming (alignment), data structures (trees and arrays), and applications in computational biology, text retrieval, and natural-language processing.
Sub-topics
Core questions
- How can a pattern be located in a text faster than naive character-by-character comparison?
- How is a large text preprocessed so that many later queries are fast?
- How is similarity between two strings defined and computed?
- How do alphabet size and string length affect the efficiency of string algorithms?
- How do exact-match methods extend to approximate or multiple-pattern matching?
Key concepts
- alphabet and string
- exact pattern matching
- Knuth-Morris-Pratt and Boyer-Moore
- tries
- suffix trees and suffix arrays
- edit distance
- sequence alignment
- approximate matching
Key theories
- Linear-time exact pattern matching
- By preprocessing the pattern to exploit information from partial matches, algorithms such as Knuth-Morris-Pratt and Boyer-Moore find all occurrences of a pattern in time linear in the text length, avoiding the quadratic cost of naive matching.
- Index structures for text
- Suffix trees and suffix arrays preprocess a text so that arbitrary pattern queries, repeats, and longest-common-substring questions can be answered quickly, trading construction cost for fast repeated search.
Clinical relevance
String algorithms are foundational to text search and bioinformatics: pattern matching powers search utilities, text editors, and intrusion detection; suffix structures index search engines and genome databases; and sequence alignment is central to comparing DNA, RNA and protein sequences in molecular biology.
History
Efficient string matching emerged in the 1970s with the Knuth-Morris-Pratt (1977) and Boyer-Moore (1977) algorithms. Suffix trees (Weiner, 1973; McCreight, 1976; Ukkonen, 1995) and later suffix arrays (Manber and Myers, 1990) gave powerful indexing, and the field expanded rapidly through computational biology, surveyed in Gusfield's 1997 text.
Key figures
- Donald Knuth
- James H. Morris
- Vaughan Pratt
- Robert Boyer
- J Strother Moore
- Dan Gusfield
Related topics
Seminal works
- knuth1977
- gusfield1997
- cormen2009
Frequently asked questions
- Why preprocess the pattern or text instead of searching directly?
- Naive matching can take time proportional to the product of pattern and text lengths. Preprocessing the pattern (as in Knuth-Morris-Pratt) gives linear-time search, and preprocessing the text into an index (suffix tree or array) lets many later queries each run far faster, which pays off when the same text is searched repeatedly.
- How are string algorithms used in biology?
- DNA, RNA and proteins are naturally represented as strings, so pattern matching locates motifs, suffix structures index genomes for fast lookup, and sequence-alignment algorithms quantify similarity between sequences to infer evolutionary relationships and function.