F03【模板】KMP 算法

#include<bits/stdc++.h>
using namespace std;
char S[11100000],s[110000];
int            pre[110000];
int main() 
{
    scanf("%s%s",S+1,s+1);
    int Slen=strlen(S+1),slen=strlen(s+1);
    pre[1]=0;
    for(int i=2,j=0;i<=slen;i++)
    {
        while(j>0 && s[i]!=s[j+1])j=pre[j];
        if(s[i]==s[j+1])j++;
        pre[i]=j;
    }

    for(int i=1,j=0;i<=Slen;i++)
    {
        while(j>0 && S[i]!=s[j+1])j=pre[j];
        if(S[i]==s[j+1])j++;
        if(j==slen){ 
			printf("%d %d\n",i-slen+1,i);
			return 0;
		} 
    }
    printf("NO\n");
    return 0;
}