KMP 字符串匹配

luckydrawbox · 2022-02-25 12:47:23 · 个人记录

求字符串 A 在字符串 B 中的每次出现的位置。

变量

函数

struct KMP{
    int nxt[N],f[N];
    void qnext(string a)
    {
        int l1=a.size();
        for(int i=1,j;i<l1;i++)
        {
            j=nxt[i];
            while(j&&a[j]^a[i])
                j=nxt[j];
            nxt[i+1]=(a[i]^a[j]?0:j+1);
        }
    }
    void qf(string a,string b)
    {
        int l1=a.size(),l2=b.size();
        for(int i=0,j=0;i<l2;i++)
        {
            while(j&&a[j]^b[i])
                j=nxt[j];
            if(!(a[j]^b[i]))
                j++;
            f[i]=j;
            if(!(f[i]^l1))
                cout<<i-l1+2<<endl;
        }
    }
};