2020-11-23

kmp算法匹配模板

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
int Next[1000006];
int Get_NEXT(string p)///找字串的
{
    Next[0]=-1;
    int j=0;
    int  k=-1;
    while(j<p.length())
    {
        if(k==-1||p[j]==p[k])
        {
            j++;
            k++;
            Next[j]=k;
        }
        else
            k=Next[k];
    }
}
int KMP(string s,string p)///主串s，字串p
{
    int i=0;
    int j=0;
    while((i<(int)(s.length()))&&(j<(int)(p.length())))
    {
        if(j==-1||s[i]==p[j])
        {
            i++;
            j++;
        }
        else
        {
            j=Next[j];
        }
        if(j>=(int)(p.length()))
        {
            return i-(int)(p.length());
        }
    }
    return 0;
}
int main()
{
    string s,p;
    cin>>s;
    cin>>p;
    Get_NEXT(p);
    cout<<KMP(s,p);
}