前缀函数
前缀函数的定义是:一个字符串最长的真前缀和真后缀。真前后缀的意思是这个前缀或者后缀不是这个字符串本身。
我们定义 $f(i)$ 的意思是这个字符串从第 $1$ 位到第 $i$ 位的字符串的前缀函数。
通过定义,我们可以暴力求出前缀函数 $f(i)$,复杂度 $O(n^2)$。
显然,这个复杂度太高了,于是我们可以尝试优化。
优化
第一个重要的观察是 相邻的前缀函数值至多增加 $1$。所以当移动到下一个位置时,前缀函数的值要么增加一,要么维持不变,要么减少。
那么我们可以对 $s[i+1]=s[f(i+1)]$ 的情况进行优化。
那么这样的话复杂度降到 $O(n^2)$。
但是,这样的复杂度对于很多题目还是太高了。于是可以考虑降低复杂度。
之前的情况只是优化了 $s[i+1]=s[f(i+1)]$ 的情况,但是没有优化其他可能。
于是,我们发现,当 $s[i+1]7\not =s[f(i+1)]$ 的时候,我们希望找到一个对于 $s[0\dots i]$ 中仅此于 $f(i)$ 的 $j$ 使得这样照样满足 $s[0\dots j – 1] = s[i – j + 1 \dots i] $。我们重新比较这一位和 $s[i + 1]$,如果一样那么 $f(i + 1)= j + 1$,否则重复以上的过程继续往下找,直到匹配或者不能再找了。
我们发现,这样的时间复杂度是 $O(n)$,满足了大部分的题目需求。
KMP
KMP,全称 Knuth–Morris–Pratt 算法,是一个用于字符串比较的算法。
这个算法的具体实现如下:
代码:
vector<int> find_occurrences(string text, string pattern) {
string cur = pattern + '#' + text;
int sz1 = text.size(), sz2 = pattern.size();
vector<int> v;
vector<int> lps = prefix_function(cur);
for (int i = sz2 + 1; i <= sz1 + sz2; i++) {
if (lps[i] == sz2) v.push_back(i - 2 * sz2);
}
return v;
}