Wing
String Algorithms
Trie (Prefix Tree)
Edward Fredkin, 1960
A tree for storing strings where each edge is labeled with a character; paths from the root spell prefixes. Insertion walks or extends the highlighted path.
CYK Parser
John Cocke, Daniel Younger & Tadao Kasami, 1967
Dynamic programming over substrings to decide if a string is in a CNF grammar.
KMP Pattern Matching
Donald Knuth, James Morris & Vaughan Pratt, 1970
A linear-time string matching algorithm that avoids redundant comparisons using a failure function to skip ahead on mismatch.
Earley Parser
Jay Earley, 1970
General CFG parsing in O(n³) worst case using sets of dotted productions per input position.
Aho–Corasick
Alfred V. Aho & Margaret J. Corasick, 1975
Builds a keyword trie with failure links (like KMP for multiple patterns) so a text can be scanned in linear time with a tiny automaton.
Manacher — Odd Palindromes
Glenn Manacher, 1975
Finds maximal odd-length palindrome radii in linear time using symmetry about the furthest known palindrome.
Boyer-Moore
Robert Boyer & J Strother Moore, 1977
An efficient string search that compares right-to-left and skips ahead using bad character and good suffix heuristics.
Z-Algorithm
Ruth Williams, 1984
Computes the Z-array in linear time: Z[i] is the length of the longest substring starting at i that matches a prefix—useful for exact pattern search.
Rabin-Karp
Michael Rabin & Richard Karp, 1987
A string searching algorithm that uses hashing to find pattern matches, verifying hash collisions with character comparison.