PrevNext
Rare
 0/31

String Searching

Authors: Benjamin Qi, Siyong Huang

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

Resources
CPC

String 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 NameDifficultyTags
KattisEasy
Show TagsKMP, Strings
POIEasy
Show TagsKMP, Strings
Baltic OINormal
Show TagsKMP, Strings
POJHard
Show TagsKMP, Strings
POIHard
Show TagsKMP, Strings
CEOIHard
Show TagsKMP
POIVery Hard
Show TagsKMP
POIVery Hard
Show TagsKMP

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 NameDifficultyTags
YSEasy
Show TagsZ
CFNormal
Show TagsDP, Strings
CFNormal
Show TagsZ
CFHard

Palindromes

Manacher

Focus Problem – read through this problem before continuing!

Manacher's Algorithm functions similarly to the Z-Algorithm. It determines 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 NameDifficultyTags
CFNormal
Show TagsStrings
CFNormal
Show TagsStrings
CFHard
Show TagsPrefix Sums, Strings

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 00, the Palindromic Tree has two empty states: length 00, and length 1-1. This is because appending a character to a palindrome increases the length by 22, meaning a single character palindrome must have been created from a palindrome of length 1-1

StatusSourceProblem NameDifficultyTags
APIOEasy
CFHard
Show TagsPrefix Sums, Strings
DMOJVery Hard

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 NameDifficultyTags
COCIVery Easy
Show TagsDFS, Strings, Trie
IOIVery Easy
Show TagsDFS, Strings, Trie
YSEasy
Show TagsGreedy, Trie
CFNormal
Show TagsStrings, Trie
COCINormal
Show TagsTrie
ACNormal
IZhOHard
Show TagsGreedy, Trie
JOIHard
Show TagsBIT, Trie
CFHard
Show TagsTree, Trie

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 NameDifficultyTags
CFEasy
Show TagsStrings
GoldNormal
Show TagsStrings
CFNormal
Show TagsStrings

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!

PrevNext