Strings -> Aho-Corasick¶

Dictionary automaton for multi-pattern matching with failure and output links.

Microtopics¶

Source	Type
cp-algorithms Aho-Corasick	`Reference`
USACO Guide string searching	`Reference`

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Finding Patterns	`CSES`	`Medium`	-	Offline Matching	Trie; Failure Links	Multi-Pattern Matching; Automata	Direct multi-pattern presence queries are the textbook Aho-Corasick use case.
String Multimatching	`Kattis`	`Medium`	Multi-Pattern-Matching	-	-	Text Scanning; Output-All	The standard “find all patterns in one text” AC problem.
Word Combinations	`CSES`	`Medium`	DP	-	-	Dictionary; Segmentation; Prefix-Automaton	Can be accelerated by automaton-style prefix matching in the dictionary.
aho_corasick	`Library Checker`	`Medium`	Multi-Pattern-Matching	-	-	Failure Links; Dictionary	Direct official benchmark for building and querying the automaton.
Counting Patterns	`CSES`	`Hard`	-	Aggregation; Offline Matching	Trie; Failure Links; Output Links	Multi-Pattern Matching; Counting	Counts all occurrences, which is where Aho-Corasick becomes especially useful.
Pattern Positions	`CSES`	`Hard`	Trie	Offline Matching	Failure Links	Multi-Pattern Matching; First Occurrence; Many-Patterns; Text-Search	A clean extension of Aho-Corasick that asks for earliest matches per pattern.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Genetic engineering	`Codeforces`	`Hard`	-	DP On Automaton; Pattern Exclusion	Trie; Failure Links; Automaton DP	DP; Automata	A classic AC-plus-DP problem for constrained string construction.

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`FINDINGPATTERNS`	Finding Patterns	`primary`	`medium`	aho-corasick automaton; failure links; multi-pattern presence queries	Note	Code

python3 scripts/generate_problem_catalog.py