Authors: Benjamin Qi, Siyong Huang
Knuth-Morris-Pratt and Z Algorithms (and a few more related topics).
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.
Strings, prefix functions
|Baltic OI||Normal||View Solution|
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.
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.
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
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.
Aho-Corasick is the combination of trie and KMP. It is essentially a trie with KMP's "fail" array.
This section is not complete.
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.