字符串模式匹配算法 KMP

子串与子序列

中文名称	常见英文名称	解释
子串	\(\tt substring\)	连续的选择一段字符（可以全选、可以不选）组成的新字符串
子序列	\(\tt subsequence\)	从左到右取出若干个字符（可以不取、可以全取、可以不连续）组成的新字符串

字符串模式匹配算法 KMP

应用：

1. 在字符串中查找子串；
2. 最小周期：字符串长度-整个字符串的 \(\tt border\) ；
3. 最小循环节：区别于周期，当字符串长度 \(n \bmod (n - nxt[n]) = 0\) 时，等于最小周期，否则为 \(n\) 。

以最坏 \(\mathcal O(N+M)\) 的时间计算 \(t\) 在 \(s\) 中出现的全部位置。

auto kmp = [&](string s, string t) {int n = s.size(), m = t.size();vector<int> kmp(m + 1), ans;s = "@" + s;t = "@" + t;for (int i = 2, j = 0; i <= m; i++) {while (j && t[i] != t[j + 1]) {j = kmp[j];}j += t[i] == t[j + 1];kmp[i] = j;}for (int i = 1, j = 0; i <= n; i++) {while (j && s[i] != t[j + 1]) {j = kmp[j];}if (s[i] == t[j + 1] && ++j == m) {ans.push_back(i - m + 1); // t 在 s 中出现的位置}}return ans;
};