前缀函数

前缀函数的定义是：一个字符串最长的真前缀和真后缀。真前后缀的意思是这个前缀或者后缀不是这个字符串本身。

我们定义 $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;
}