PrevNext
Rare
 0/16

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 NameDifficultyTagsSolution
KattisEasy
Show Tags

Strings

Show Sketch
POJHard
Show Tags

Strings

Show Sketch

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 NameDifficultyTagsSolution
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 NameDifficultyTagsSolution
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 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 NameDifficultyTagsSolution
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 NameDifficultyTagsSolution
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 NameDifficultyTagsSolution
GoldNormal
Show Tags

Strings

External Sol
CFNormal
Show Tags

Strings

Check CF

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

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:

Give Us Feedback on String Searching!

PrevNext