KMP算法的next数组，存放的是子字符串(长度较小的字符串)的最长前缀后缀公共元素长度！！！

图片说明

最常用的求next数组，也可以用来求字符串可能存在的循环节：

void getnext(char s[],int len){
    int j=0,k=-1;
    next[0] = -1;
    while(j < len){
        if(k == -1 || s[j] == s[k])
            next[++j] = ++k;
        else
            k = next[k];
    }
}
//1231231234
//-1 0 0 0 1 2 3 4 5 6

另一种优化了的求next数组

void getnext(char s[],int len){
    int j=0,k=-1;
    next[0] = -1;
    while(j < len){
        if(k == -1 || s[j] == s[k]){
            j++,k++;
            if(s[j] != s[k])
                next[j] = k;
            else
                next[j] = next[k];
        }
        else
            k = next[k];
    }
}

kmp算法代码：

#include <bits/stdc++.h>
using namespace std;
const int maxx = 100010;
int next[maxx];
char s1[maxx],s2[maxx];
void getnext(char s[],int len){
    int j=0,k=-1;
    next[0] = -1;
    while(j < len){
        if(k == -1 || s[j] == s[k]){
            j++,k++;
            if(s[j] != s[k])
                next[j] = k;
            else
                next[j] = next[k];
        }
        else
            k = next[k];
    }
}
int kmp(char s1[],char s2[])
{
    getnext(s2,strlen(s2));
    int i=0,j=0;
    int l1 = strlen(s1),l2 = strlen(s2);
    while(i < l1 && j < l2){
        if(j == -1 || s1[i] == s2[j])
            i++,j++;
        else
            j = next[j];
    }
    if(j == l2)
        return i-j;
    return -1;
}
int main()
{
    scanf("%s",s1);
    scanf("%s",s2);
    cout<<kmp(s1,s2);
    return 0;
}