数据结构实验之串三：KMP应用（KMP模板）

数据结构实验之串三：KMP应用（KMP模板）

 AC_Code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
using namespace std;
typedef long long ll;
int Nex[1000000];
char st[1000000];
char str[1000000];

void Find_Nex()
{
    int i=0,j=-1;
    Nex[0]=-1;
    int len=strlen(str);
    while( i<len )
    {
        if( j==-1 || str[i]==str[j] )
        {
            i++;
            j++;
            Nex[i]=j;
        }
        else j=Nex[j];
    }
}

void kmp()
{
    int i=0,j=0;
    int len1=strlen(st);
    int len2=strlen(str);
    while( i<len1&&j<len2 )
    {
        if( j==-1 || str[j]==st[i])
        {
            i++;
            j++;
        }
        else j=Nex[j];
    }
    if( j==len2 ) cout<<i-j+1<<endl;
    else cout<<"-1"<<endl;
}


int main()
{
    while(~scanf("%s",st))
    {
        scanf("%s",str);
        memset(Nex,0,sizeof(Nex));
        Find_Nex();
        kmp();
    }
    return 0;
}