KMP

做法

如何判断一个字符串在另一个字符串里面出现了几次, 可以用哈希, 不过可能被 Hack 这里介绍一种总时间 \(O(N)\) 的写法

记 \(F(i)\) 表示字符串中前缀 \([1\) ~ \(i]\) 中最长真前后缀的长度

我们可以写出这样一个地推式

\(F(i) = \begin{cases}F(i - 1)&不是当前字符\\i + 1&是当前字符\end{cases}\)

另绿色的是 \(i - 1\) 的最长真前后缀, 若第一个绿色部分后面能与 \(i\) 匹配, 则最长真前后缀 = \(i - 1\) 的 $ + 1$

否则看前面的红色真前缀和真后缀最比较, 图上的红色的区间

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

int n, m, p[N];
string s, t;

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> s;
  n = s.size();
  s = ' ' + s;
  for(int i = 2, j = 0; i <= n; ++i){
    for(; j && s[i] != s[j + 1]; j = p[j]){
    }
    j += (s[i] == s[j + 1]);
    p[i] = j;
  }
  for(int i = 1; i <= n; ++i){
    cout << p[i] << ' ';
  }
  return 0;
}

时间复杂度

每次跳至少会让所在位置 -1, 每次最多只会让变量 +1, 每 +1 才能减一次一, 所以时间复杂度为 \(O(2n)\)