经典KMP算法判断

#include
#include
using namespace std;
const int M=1e6+10;
void Getnext(string t,int next[])
{
    int i=0,j=-1;
    next[0]=-1;
    int len=t.size();
    while(i     {
        if(j==-1||t[i]==t[j])
        {
            next[++i]=++j;
            if(t[i]==t[j])
                next[i]=next[j];
        }
        else
            j=next[j];
    }
}
bool index_KMP(string s,string t,int next[])
{
    int i=0,j=0;
    int len1=s.size(),len2=t.size();
    while(i     {
        if(j==-1||s[i]==t[j])
        {
            i++;j++;
        }
        else
        {
            j=next[j];
        }
    }
    if(j>=len2)
        return true;
    else
        return false;
}
int main()
{
    string s,t;
    int i;
    while(cin>>s)
    {
        int next[M+50]= {0};
        cin>>t;
        Getnext(t,next);
        int flag=index_KMP(s,t,next);
        if(flag==0)
            cout<<"NO"<         else
            cout<<"YES"<     }
}