String matching: KMP, Z-function and rolling hashes · 1 of 2 Advanced
KMP and the prefix function
Build the prefix function, use it to find every copy of a pattern in linear time, and read borders and periods from it.
- Prefix function. Knuth-Morris-Pratt algorithm Derives the linear build from the naive one in two steps, then uses the table to count prefix occurrences and distinct substrings, compress a string and build an automaton. cp-algorithms.com (opens in a new tab)
- String Searching KMP and the Z algorithm side by side, then Manacher’s palindrome algorithm, tries and Aho-Corasick for many patterns at once. usaco.guide (opens in a new tab)
- 前缀函数与 KMP 算法 (Prefix function and KMP) The same construction as cp-algorithms, plus a section on string periods that goes further than the Repeated Substring Pattern check here. oi-wiki.org (opens in a new tab)