代码：

const int mod=998244353,MAXN=1e6+8;
int nex[MAXN];
void getnext(char p[],int len){
    memset(nex,0,sizeof(nex))
    int k=nex[0]=-1,i=0;
    while(i<len){
        while(k!=-1&&p[i]!=p[k])k=nex[k];
        nex[++i]=++k;
    }
}
void kmp(char s[],char p[]){
    int lens=strlen(s),lenp=strlen(p);
    getnext(p,lenp);
    for(int i=0,j=0;i<lens;){//如果看是否找到，i<lens&&j<lenp;
        while(j!=-1&&s[i]!=p[j])j=nex[j];
        ++i,++j;
        if(j==lenp){
            printf("%d\n",i-j+1);//输出所有出现的位置
            j=nex[j];
        }
    }
    //if(j==lenp)return i-j;
    //return -1
}

假设上面是字符串s，下面是p。

假设匹配到了字符a！= b。
当前next[j]的值就是串3的长度

因为串1234都是一样的，所以j跳回到串3的最后面。

串2和3是相等的，所以直接比较串2和串3后面的字符就行了
最麻烦的就是next数组，next[j]是除去字符j后p[0,j-1]这个子串里前缀和后缀相等的最长长度。
这里只考虑出现不同字符的情况，否则就直接+1
k最开始是指向字符a的，但是a！=j指向的字符，所以k=next[k]
即k指向前k个字符组成的串的next值，就是下图所示。

如图，又有4个子串是一样的，继续比较k指向的字符和j指向的字符就行了，显然就是一个递归的过程。