PrevNext
Rare
 0/19

String Searching

Authors: Benjamin Qi, Siyong Huang

Knuth-Morris-Pratt and Z Algorithms (and a few more related topics).

Resources
CPCString Matching, KMP, Tries
CP2

Single String

KMP

Knuth-Morris-Pratt, or KMP, is a linear time string comparison algorithm that matches prefixes. Specifically, it computes the longest substring that is both a prefix and suffix of a string, and it does so for every prefix of a given string.

StatusSourceProblem NameDifficultyTagsSolutionURL
KattisEasy
Show Tags

Strings

Show Sketch
POIEasy
Show Tags

Strings, prefix functions

External Sol
Baltic OINormalView Solution
POJHard
Show Tags

Strings

Show Sketch
CEOIHardView Solution

Z Algorithm

The Z-Algorithm is another linear time string comparison algorithm like KMP, but instead finds the longest common prefix of a string and all of its suffixes.

StatusSourceProblem NameDifficultyTagsSolutionURL
YSEasyView Solution
CFNormal
Show Tags

Strings, DP

Check CF
CFHardCheck CF

Palindromes

Manacher

Manacher's Algorithm is functionally similarly to the Z-Algorithm and can compute information about palindromes. It can determine the longest palindrome centered at each character.

Don't Forget!

If s[l, r] is a palindrome, then s[l+1, r-1] is as well.
StatusSourceProblem NameDifficultyTagsSolutionURL
CFNormal
Show Tags

Strings

Check CF
CFNormal
Show Tags

Strings

Check CF
CFHard
Show Tags

Strings, Prefix Sums

Check CF

Palindromic Tree

A Palindromic Tree is a tree-like data structure that behaves similarly to KMP. Unlike KMP, in which the only empty state is , the Palindromic Tree has two empty states: length , and length . This is because appending a character to a palindrome increases the length by , meaning a single character palindrome must have been created from a palindrome of length

StatusSourceProblem NameDifficultyTagsSolutionURL
APIOEasy
CFHard
Show Tags

Strings, Prefix Sums

Check CF
DMOJVery HardCheck DMOJ

Multiple Strings

Tries

A trie is a tree-like data structure that stores strings. Each node is a string, and each edge is a character. The root is the empty string, and every node is represented by the characters along the path from the root to that node. This means that every prefix of a string is an ancestor of that string's node.

StatusSourceProblem NameDifficultyTagsSolutionURL
YSEasyView Solution
CFNormal
Show Tags

Strings

Check CF
CFHard
Show Tags

Trie, Tree

Check CF

Aho-Corasick

Aho-Corasick is the combination of trie and KMP. It is essentially a trie with KMP's "fail" array.

Warning!

Build the entire trie first, and then run a BFS to construct the fail array.

StatusSourceProblem NameDifficultyTagsSolutionURL
GoldNormal
Show Tags

Strings

External Sol
CFNormal
Show Tags

Strings

Check CF

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

1731 Word Combinations -> trie 1753 String Matching -> string search 1732 Finding Borders -> string search 1733 Finding Periods -> string search 1110 Minimal Rotation -> string search 1111 Longest Palindrome -> string search 1112 Required Substring -> string search

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Give Us Feedback on String Searching!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.

PrevNext