本文主要是介绍KMP 详解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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;
} 
这篇关于KMP 详解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
