Rare
0/16

# String Searching

Authors: Benjamin Qi, Siyong Huang

### Prerequisites

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.

Resources
HR
CFshorter code
cp-algo

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