Chapter 5: Strings

Overview

String problems are their own world in competitive programming — they look like they need brute force, but they have linear and near-linear solutions once you know the right technique. This chapter teaches two distinct kinds of tool, and it is worth keeping them apart in your head:

• Hashing as a pragmatic comparator. Polynomial hashing turns substring equality into modular arithmetic. It is fast, easy to write, and good enough to win most contest problems — but it is probabilistic. A hash match is a fingerprint match, not a proof of equality.
• Deterministic string algorithms. KMP, Z, Manacher, suffix arrays, suffix automata, Aho-Corasick, eertree, and Lyndon factorization all give exact answers in linear or near-linear time. They cost more thought to implement, but they never lie.

The chapter starts with hashing because it is the cheapest unlock, then teaches the deterministic toolkit roughly in order of how often each one shows up under pressure.

Navigation

Coming from: Chapter 4 — Dynamic Programming — DP state design from 1D recurrences to bitmask and tree DP
Going to: Chapter 6 — Advanced Graph Algorithms — advanced graph decompositions, flows, and tree techniques

Topics at a Glance

#	Topic	Difficulty	Key Trigger Phrase
01	String Hashing	Beginner	"Compare substrings in O(1)" or "find matching patterns"
02	KMP and Z-Function	Beginner	"Find pattern in text" in O(n + m)
03	Manacher's Algorithm	Intermediate	"Find all palindromic substrings" in O(n)
04	Suffix Array	Advanced	"Distinct substrings," "longest repeated substring," or "pattern count"
05	Suffix Automaton	Advanced	"Smallest DFA for all substrings" — online substring queries
06	Aho-Corasick	Advanced	"Search for multiple patterns simultaneously"
07	Palindromic Tree (Eertree)	Advanced	"Count distinct palindromic substrings" online
08	Lyndon Factorization	Advanced	"Lexicographically smallest rotation" or cyclic string problems

Two reading paths

Minimal foundation — what you need before any string problem feels approachable:

1. String Hashing — polynomial hashing compares arbitrary substrings in O(1) after O(n) preprocessing. The first tool to try, and the one most contest problems give in to.
2. KMP and Z-Function — linear-time exact pattern matching. Z is usually easier to implement; KMP's failure function generalizes to more pattern-recognition problems.
3. Manacher's Algorithm — palindromes show up disguised as range queries; Manacher gives you all of them in O(n).

First advanced tool — when the foundation is not enough, reach for one of:

• Aho-Corasick for multi-pattern search over a fixed dictionary. Builds directly on the Trie from Chapter 2 plus KMP-style failure links.
• Suffix Array for distinct-substring counts, longest repeated substring, and pattern-count queries on a single fixed text.
• Suffix Automaton when you need online substring queries or substring statistics.

Cross-Chapter Connections

• String Hashing uses modular arithmetic from Math Fundamentals in Chapter 7
• Aho-Corasick builds on the Trie data structure from Chapter 2
• Suffix Array uses Sorting ideas from Chapter 1 (radix sort / doubling)
• String problems often combine with DP — Bitmask or DP — Digit from Chapter 4
• Manacher and Palindromic Tree both solve palindrome problems — Manacher for offline, Eertree for online counting

---

File Listing

File	Topic	Level
string-hashing	String Hashing	⭐
kmp-and-z-function	KMP and Z-Function	⭐
manacher	Manacher's Algorithm	⭐⭐
aho-corasick	Aho-Corasick	⭐⭐⭐
suffix-array	Suffix Array	⭐⭐⭐
suffix-automaton	Suffix Automaton	⭐⭐⭐
palindromic-tree	Palindromic Tree (Eertree)	⭐⭐⭐
lyndon-factorization	Lyndon Factorization	⭐⭐⭐

Suggested Reading Order

1. string-hashing — polynomial hashing for O(1) substring comparison
2. kmp-and-z-function — linear-time pattern matching fundamentals
3. manacher — find all palindromic substrings in O(n)
4. aho-corasick — multi-pattern matching via failure links on trie
5. suffix-array — sorted suffixes for substring queries
6. suffix-automaton — smallest DFA accepting all suffixes
7. palindromic-tree — online palindrome counting and enumeration
8. lyndon-factorization — decompose into Lyndon words for cyclic problems