KMP算法

大意

大串a中找小串b

小串处理

\(next[i]\)表示\(b[i]\)匹配过程中失配情况下可以向前跳几个字符,意思就是b的前i个的公共前后缀的最大长度

如\(B="ABCBCABCD",i=7\)时\(next[i]\)为\(3\)。

处理：如果\(b[next[x-1]]==b[x]\)，则\(next[x]=next[x-1]+1\)，否则在\(x-1\)的公共前后缀中找，迭代这一过程

\(query(x,y)=\{^{\ next[x-1]+1\ \ \ (b[next[x-1]]==y)}_{\ query(next[x-1],y)\ \ \ (b[next[x-1]]!=y)}\)

\(next[i]=query(i,b[i])\)

可以用\(while\)实现

大串处理

若现在找到大串的\(p1\)位置与小串的\(p2\)位置而失配，那么接下来找\(b[next[p2]+1]\)是否等于a[p1]，如果依然不等于，就在next[p2]+1里面继续找

相当于每次讲\(p2\)迭代为\(next[p2]\)

代码

#include<bits/stdc++.h>
using namespace std;
int next[1000010];
char a[1000010],b[1000010];
int lena,lenb;
int p1,p2;
int main(){
    cin>>a+1>>b+1;
    lena=strlen(a+1);
    lenb=strlen(b+1);
    for(int i=2;i<=lenb;i++){     
        while(p2&&b[i]!=b[p2+1]){
            p2=next[p2];
        }
        if(b[p2+1]==b[i]){
            p2++;
        }
        next[i]=p2;
    }
    p2=0;
    while(p1<=lena){
        while(p2>0&&b[p2+1]!=a[p1]){
            p2=next[p2];
        }
        p2+=b[p2+1]==a[p1];
        p1++;
        if(p2==lenb){
            cout<<p1-lenb<<'\n';
            p2=next[p2];
        }
    }
    for(int i=1;i<=lenb;i++){
        cout<<next[i]<<' ';
    }
    return 0;
}

KMP算法简介

原文：https://www.cnblogs.com/xiong-6/p/11853680.html