子串与子序列
| 中文名称 | 常见英文名称 | 解释 |
|---|---|---|
| 子串 | \(\tt substring\) | 连续的选择一段字符（可以全选、可以不选）组成的新字符串 |
| 子序列 | \(\tt subsequence\) | 从左到右取出若干个字符（可以不取、可以全取、可以不连续）组成的新字符串 |
字符串模式匹配算法 KMP
应用：
- 在字符串中查找子串；
- 最小周期：字符串长度-整个字符串的 \(\tt border\) ；
- 最小循环节：区别于周期，当字符串长度 \(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;
};
