网站首页模板程序开发工程师

KMP数组存的是什么

对于一个字符串 b,下标从1开始。

则kmp[i]表示 以i结尾的连续子串 = s的前缀的最大值（等价于前缀最大结尾处）

如何求KMP

假设 i 以前的KMP都被求出来了。

j 表示上一个字符可以成功匹配的长度（等价于下标）

如果b[j+1] != b[i]下一个位置匹配不上（即不能成为前缀）

则，让j = kmp[j] 即成为以j结尾的 连续子串 的 最长前缀 尾部的下标

退出循环后，若还能匹配上则j++(本质是，加上i的贡献。因为j = 0时可能匹配不上)

然后让kmp[i] = j即可。

运用kmp

和求kmp差不多，如果匹配不上，求让a[i]和以j结尾的连续子串的最长前缀匹配。（放宽要求）

算法正确性证明

用哲学的话来说就是，每一次失败都会让我变得更强大。

当匹配不上时，匹配串b至少会前移1位，由指针的思想。O(n)可证。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+7;
int kmp[N];
string a,b;
int j;
int main(){cin>>a>>b;a = " "+a;b = " "+b;for(int i = 2;i < b.size();i++){while(j&&b[j+1] != b[i]){j = kmp[j];}if(b[j+1] == b[i])j++;kmp[i] = j;}j = 0;for(int i = 1;i < a.size();i++){while(j&&a[i] != b[j+1]){j = kmp[j];}if(b[j+1] == a[i])j++;if(j == b.size()-1){cout<<i-(b.size()-1)+1<<endl;j=kmp[j];}}for (int i=1;i < b.size();i++)cout<<kmp[i]<<" ";return 0;
}