String Algorithms
Hashing, pattern matching, suffix structures and palindromes: the toolbox for text problems.
12 articles~93 min total
0/12
Fundamentals
- String Hashing and Rabin-KarpCompare any two substrings in O(1) after O(n) preprocessing with polynomial hashes, and use rolling hashes to search for patterns.8 minIntermediate
- Prefix Function and Knuth-Morris-PrattCompute the longest proper border of every prefix in O(n), and use it for pattern matching, string periods and counting occurrences.6 minIntermediate
- Z-functionFor every position, the length of the longest common prefix with the whole string, in O(n), and its uses in matching and periods.5 minIntermediate
- Suffix ArraySort all suffixes of a string, build the array in O(n log n) by prefix doubling, compute LCP with Kasai's algorithm, and use both for substring search and counting distinct substrings.11 minAdvanced
- Aho-Corasick AlgorithmSearch for many patterns in a text at once by building a trie with failure links, and use the resulting automaton for counting strings that avoid patterns.8 minAdvanced
- Rabin-Karp Pattern MatchingFind a pattern (or many patterns of equal length) in a text with a rolling hash, updating the window hash in O(1).7 minIntermediate
Advanced
- Suffix Tree and Ukkonen's AlgorithmA compressed trie of all suffixes that answers substring questions in O(pattern length), built online in linear time with Ukkonen's algorithm.9 minAdvanced
- Suffix AutomatonThe smallest automaton that accepts exactly the suffixes of a string: built online in linear time, it counts distinct substrings, occurrences and longest common substrings.10 minAdvanced
- Lyndon FactorizationSplit a string uniquely into non-increasing Lyndon words in O(n) with Duval's algorithm, and use it to find the minimal cyclic shift.6 minAdvanced
Tasks
- Expression ParsingEvaluate arithmetic expressions with priorities, parentheses, unary minus and right-associative operators using two stacks or recursive descent, in O(n).11 minIntermediate
- Manacher's Algorithm: All Palindromic SubstringsFind the longest palindrome centered at every position, and hence count all palindromic substrings, in O(n).6 minAdvanced
- Finding Repetitions (Main-Lorentz)Find all squares (a substring written twice in a row) in O(n log n) with divide and conquer and the Z-function.6 minAdvanced