Strings

String problems split cleanly into three families: matching (find a pattern), structure (borders, periods, palindromes) and indexing (answer many queries about all substrings at once).

Basics

• String Fundamentals — periods, borders, lexicographic order
• String Hashing · Rolling Hash · Polynomial Hashing

Pattern Matching

• Prefix Function (KMP) · KMP Algorithm
• Z-Function · Z-Algorithm
• Rabin-Karp
• Boyer-Moore · Bitap · Shift-Or
• Aho-Corasick (multi-pattern) · Wu-Manber · Commentz-Walter

Palindromes

• Palindromes
• Manacher’s Algorithm
• Palindromic Tree (Eertree)

Suffix Structures

• Suffix Array · SA-IS · DC3 · Kasai (LCP)
• Suffix Automaton
• Suffix Tree · Ukkonen · McCreight · Weiner
• Trie and Compressed Trie

Other

• Lyndon Words · Duval’s Algorithm
• Booth’s Algorithm (least rotation)
• String DP
• Compression and Run-Length