ＫＭＰ算法数组下标从0和数组下标从1开始
我在运用KMP时，总时会搞混如果数组下标为0时要如何用写，下标为1时要如何写。
当下标为0时kmp
void kmp(int len)
{//下标为0 时vector<int> f(n,-1);for(int i = 1;i < len;i++){ // 每次更新的是 下标i // 当第 i+1不匹配是 跳到 f[i]的位置上，看小标为 s[f[i]+1] == s[i] 不等可以继续跳 int j = f[i-1];while(j != -1 && s[j+1] != s[i]){s[j] = f[j];}if(s[j+1] == s[i]){f[i] = j+1;}else{f[i] = j;}}
}当下标为1时，KMP算法：
#include<iostream>
#include<cstring>
#define MAXN 1000010
using namespace std;
int kmp[MAXN];
int la,lb,j;
char a[MAXN],b[MAXN];
int main()
{cin>>a+1;cin>>b+1;la=strlen(a+1);lb=strlen(b+1);for (int i=2;i<=lb;i++){ while(j&&b[i]!=b[j+1])j=kmp[j]; if(b[j+1]==b[i])j++; kmp[i]=j;}j=0;for(int i=1;i<=la;i++){while(j>0&&b[j+1]!=a[i])j=kmp[j];if (b[j+1]==a[i]) j++;if (j==lb) {cout<<i-lb+1<<endl;j=kmp[j];}}for (int i=1;i<=lb;i++)cout<<kmp[i]<<" ";return 0;
}其实基本一样的只是一个初始化为-1，一个初始化为0。而next中记录的意义为前缀字符串和后缀字符串的长度，当i+1不匹配时，可以跳到 next[i] (因为next[i] 在进行 next[i]+1 是否配对成功)
还有一种是 在 KMP 中是记录next[i+1]的下标。
void getNext(char *p,int plen)
{// 记录 i+1 的跳的位置 Next[0] = 0;Next[1] = 1;for(int i = 2;i < plen;i++){int j = Next[i];while(j&&p[i] != p[j]){j = Next[j];}if(p[i] == p[j]){Next[i+1] = j+1;}else{Next[i+1] = 0;}}
} 这种Next是直接记录当i不匹配时，直接跳到下标为Next[i]进行配对，它记录的是Next 时最长前缀 和最长后缀的长度后 ，最长前缀的长度还+1。所以直接比较Next[i]就可以了。