- Atlas
- Computer Science
- String Algorithms
String Algorithms
String algorithms are the procedures computers use to find, compare, compress, and index sequences of symbols—text, DNA, log files, the bytes of a disk image.
7 frameworks, from 1906 to today · Algorithms · Computer Science
Overview
String algorithms are the procedures computers use to find, compare, compress, and index sequences of symbols—text, DNA, log files, the bytes of a disk image. A string here is just an ordered sequence of characters drawn from some alphabet, and the field's central problems are deceptively simple to state: does this pattern occur in that text, and where1? How different are two strings? How small can we store a string while still being able to search it? What the field has discovered is that these questions hide deep structure, and that the right way to exploit that structure has changed several times over.
Combinatorics on Words: The Mathematical Foundation
Before there were algorithms there was a body of pure mathematics about the structure of sequences. Combinatorics on words studies strings as mathematical objects: which patterns must appear in any long enough string, how strings can be built from repetitions, and what constraints force periodicity2. Its founding figure is Axel Thue, who in a series of papers around 1906–1912 constructed an infinite string over three letters containing no two adjacent identical blocks—the first squarefree word—and proved results about avoiding repetitions that anticipated much later work. The Russian school around Andrey Markov and later the French school around Marcel-Paul Schützenberger developed the theory of words (finite or infinite sequences) through the mid-twentieth century.
The field's most famous single result is the Fine–Wilf theorem (Nathan Fine and Herbert Wilf, 1965): if a string has two periods whose sum is at least the string's length plus the greatest common divisor of the periods, then it has a smaller period dividing both. This sounds technical, but it is exactly the kind of structural fact that string algorithms later lean on—it tells you that periods cannot be "almost" independent, which bounds how complicated a string's repetitive structure can be. Combinatorics on words supplied the vocabulary—borders, periods, primitive words, Lyndon words—that every later algorithm speaks.
Exact Pattern Matching: From Brute Force to Linear Time
The practical problem that launched the field is exact pattern matching: given a pattern of length m and a text of length n, report every position where the pattern occurs3. The obvious method compares the pattern against each text position in turn, which can cost on the order of m·n comparisons—bad when the pattern is long and the text is full of near-misses.
The turning point came in 1977, when Donald Knuth and Vaughan Pratt, and independently James Morris, published what became the Knuth–Morris–Pratt (KMP) algorithm. Its idea: when a mismatch occurs, the characters already matched tell you something. If the pattern's prefix of length k is also a suffix of what you just matched, you can slide the pattern forward without re-examining those characters. Precomputing this "failure function" for the pattern makes the whole search run in time proportional to n + m. In the same period Robert Boyer and J Strother Moore (1977) took the opposite tack: compare the pattern from right to left, and use the mismatched character to skip large chunks of text—often far faster than linear in practice, though worst-case linear only with later refinements.
A different and influential idea came from Rabin and Karp (1987): hash the pattern and each text window, and compare hashes rather than characters, verifying only on a hash match. This fingerprinting approach made pattern matching a matter of arithmetic and opened the door to randomized algorithms throughout the field. By the 1990s the theoretical picture was settled—linear-time exact matching is possible and the lower bounds match—and attention moved to harder variants.
Approximate Matching and Edit Distance
Real data is noisy: a search query has a typo, a DNA read has sequencing errors. Approximate string matching asks for occurrences of a pattern allowing a bounded number of insertions, deletions, and substitutions. The measure of difference is the edit distance (Levenshtein distance), the minimum number of such operations turning one string into another456. Vladimir Levenshtein defined it in 1965; the dynamic-programming recurrence that computes it—fill a table where each cell is the cheapest way to align prefixes—is one of the most-taught algorithms in computer science.
The naive table costs time and space proportional to m·n. A long line of work attacked this. In 1980 Peter Sellers and others framed approximate matching as a dynamic program over the text; Esko Ukkonen (1985) showed how to cut the computation to the diagonal band of the table where the edit budget allows, giving time proportional to k·n for edit distance k. Gene Myers (1999) found an algorithm running in time proportional to the edit distance times the text length, which made fast diff tools possible—the diff program that compares files descends from this line of work. Approximate matching also connects to sequence alignment in bioinformatics, where the same dynamic programs, with tuned scoring, align genomes; the Smith–Waterman algorithm (1981) for local alignment is a direct descendant.
Dictionary Compression and the Lempel–Ziv Revolution
Compression asks how to represent a string in fewer bits. The dominant family exploits repetition: replace repeated substrings with short references. Abraham Lempel and Jacob Ziv published two landmark papers, in 1977 and 1978, defining what are now called LZ77 and LZ787. LZ77 scans the text and, at each point, emits a pointer to the longest earlier substring that matches what follows—so a repeated phrase costs one reference instead of its full length. LZ78 builds an explicit dictionary of phrases as it goes, emitting an index into that dictionary7. Both are dictionary methods: the compressed form is a sequence of references into previously seen material879.
These ideas became the backbone of practical compression. The DEFLATE format (used in zip and gzip), the LZW variant (Terry Welch, 1984) used in GIF images, and later LZMA all descend from Lempel–Ziv71011. The theoretical question—how well can any such scheme do—was answered in part by grammar-based compression, which represents a string by a context-free grammar whose language is exactly that one string12. A grammar can capture nested and overlapping repetition that a flat dictionary cannot, and the smallest such grammar is a natural measure of a string's compressibility. The links between grammar size, LZ parsing, and the string's repetitiveness became a rich research area from the 1990s onward.
Suffix-Based Indexing: Searching Without Rescanning
If you must answer many queries against a fixed text—a genome, a document collection—rescanning it each time is wasteful. Suffix-based indexing preprocesses the text once so that any pattern can be located quickly. The key object is the suffix array: the list of all starting positions of the text's suffixes, sorted alphabetically13. Because every occurrence of a pattern is a prefix of some suffix, and sorted suffixes cluster by prefix, a binary search over the suffix array finds all occurrences in time proportional to the pattern length times a logarithm.
The suffix array was described by Manber and Myers in 1990 (building on earlier ideas), and its compactness—one integer per text position—made it attractive against the older suffix tree, a trie-like structure of all suffixes introduced by Peter Weiner in 1973 and made practical by Edward McCreight (1976) and Ukkonen (1995). Suffix trees support linear-time construction and fast queries but use much more memory. The suffix array, with the auxiliary LCP array (longest common prefix between adjacent suffixes, computable in linear time by Kasai and colleagues in 2001), gives most of the same power in far less space. Linear-time suffix array construction was achieved by several groups around 2003 (Kärkkäinen and Sanders; Kim, Sim, Park, and Park), settling the construction problem.
Compressed and Succinct Indexing: Indexing the Index
A suffix array still costs several times the text size in bits. Succinct and compressed indexing asks whether the index can be stored in space close to the compressed text itself while still answering queries14. The FM-index, introduced by Paolo Ferragina and Giovanni Manzini in 2000, is the landmark: it combines the Burrows–Wheeler transform (1994) with a compressed representation of the transformed text and a small auxiliary structure, and answers pattern queries by working backward through the pattern one character at a time. Its space is proportional to the compressed text, and it became the engine of modern read-alignment tools in genomics, such as Bowtie and BWA.
The broader program—succinct data structures, storing data in space near the information-theoretic minimum while supporting fast operations—was articulated by Guy Jacobson in 1989 and matured through the 2000s. Compressed indexing now spans suffix-array-based, FM-index-based, and grammar-based indexes, each trading space against query speed differently. The unifying insight is that the repetitiveness of real data—genomes, versioned source code, web crawls—can be measured and exploited, so that the index shrinks along with the data.
Where the Field Stands
Today string algorithms is a mature but active area. Exact matching is solved in the classic model, and research has moved to dynamic and streaming settings, where the text changes or arrives piecemeal. Approximate matching and edit distance remain central, with recent work on faster algorithms for large alphabets and on sketching distances without full computation. Compression and indexing have converged: the frontier is repetition-aware indexing that exploits the massive redundancy in collections of similar genomes or version histories, and grammar-compressed structures that answer queries directly on the grammar. The questions still open are largely about the limits: how small can an index be while staying fast, how quickly can edit distance be computed in the worst case, and how to handle the adversarial or noisy inputs that real systems meet. The field's history is a record of finding structure in sequences that nobody expected to be there—and then building algorithms that depend on it.
References
- String (computer science) (introduction, Formal theory), Wikipedia
- Combinatorics on words, Wikipedia
- String-searching algorithm, Wikipedia
- String metric, Wikipedia
- Edit distance, Wikipedia
- Levenshtein distance, Wikipedia
- LZ77 and LZ78, Wikipedia
- Lempel–Ziv–Storer–Szymanski, Wikipedia
- Dictionary coder, Wikipedia
- Lempel–Ziv–Welch, Wikipedia
- Deflate, Wikipedia
- Grammar-based code, Wikipedia
- Suffix array, Wikipedia
- Compressed suffix array, Wikipedia
The frameworks of String Algorithms
Each framework is a way of working the field has used: when it held, and the question it answers.
- 1906-Present
- 1965-Present
- 1973-Present
- 1977-Present
- 1977-Present
- 1989-Present
Compressed and Succinct Indexing
How can we store an index in small space?
- 1990-Present
How the ideas connect
Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.
String-searching algorithm influenced by Combinatorics on Words
The Knuth–Morris–Pratt algorithm's failure function is built on the notion of borders and periods of words, central to combinatorics on words.
Carried by Donald Knuth; Vaughan Pratt; James Morris.
Compressed and Succinct Indexing grew out of Suffix-Based Indexing
The FM-index and other compressed indexes are built on suffix arrays and suffix trees, compressing them while preserving query capabilities.
Carried by Paolo Ferragina; Giovanni Manzini.
Grammar-based code influenced by Dictionary coder
Grammar-based compression generalizes dictionary methods like LZ78, using hierarchical grammars to capture nested repetitions that flat dictionaries cannot.
Beyond the field
Where String Algorithms's ideas came from in other fields, and what they led to there.
Approximate string matching influenced Pairwise Sequence Alignment in Bioinformatics
Approximate string matching, formalised in the Levenshtein distance and the Needleman-Wunsch dynamic programming formulation, provided the algorithmic core of pairwise sequence alignment. Needleman and Wunsch's 1970 method is a direct application of edit-distance dynamic programming to biological sequences.
Carried by Saul Needleman; Christian Wunsch.
String-searching algorithm influenced Heuristic Database Search in Bioinformatics
String-searching algorithms, notably the Smith-Waterman and FASTA work building on exact string matching, provided the computational primitives that heuristic database search adapted for rapid similarity screening of sequence libraries.
Carried by David Lipman.
Combinatorics on Words influenced by Invariant Theory and Symmetric Group Representation Theory in Algebraic Combinatorics
The theory of words borrowed heavily from invariant theory and symmetric-group representation theory: Schützenberger and others applied the Robinson–Schensted correspondence and Young-tableau methods to study free monoids, plactic monoids and word combinatorics.
Carried by Marcel-Paul Schützenberger.
Combinatorics on Words influenced by Generating Functions in Combinatorics
Combinatorics on words grew out of the enumerative tradition: Thue's 1906 work on word sequences and later Lyndon and Schützenberger's studies used generating-function and enumeration techniques from classical combinatorics to count words, necklaces and free-monoid elements.
Carried by Axel Thue; Roger Lyndon; Marcel-Paul Schützenberger.
String-searching algorithm influenced Pairwise Sequence Alignment in Bioinformatics
String-searching algorithms were taken up in bioinformatics for pairwise sequence alignment: exact and approximate pattern search underpin database similarity search (BLAST, FASTA), which uses the string-matching machinery developed in computer science.
Carried by Stephen Altschul; David Lipman.
Compressed and Succinct Indexing influenced by Information retrieval in Information Science
Compressed and succinct indexing arose within information retrieval to store large text collections compactly while supporting pattern and phrase queries; the FM-index and related structures were motivated by full-text retrieval needs.
Carried by Paolo Ferragina; Giovanni Manzini.

String Algorithms is a planet in Nousfarer
Its city has a tower for each of these 7 frameworks. Land, walk in, and climb one concept at a time.
Land on String AlgorithmsRelated fields
Fields its ideas are linked to
- Bioinformatics 3 links
- Algebraic Combinatorics 1 link
- Information Science 1 link
- Combinatorics 1 link
More in Algorithms
- Algorithms
- Approximation Algorithms
- Computational Geometry
- Data Structures
- Distributed Algorithms
- Graph Algorithms
- Online Algorithms
- Parallel Algorithms
- Parameterized Algorithms
- Randomized Algorithms
- Streaming Algorithms
See where String Algorithms sits on the Map of Human Knowledge