SDUTOJ 2772 KMP简单应用

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvUl9NaXNheWE=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center">

#include<iostream>

#include<string.h>

#include<stdio.h>

#define N 10000001

using namespace std;

char s[N],s1[N];

int next[N];

void getnext(char s1[])

{

	int j=-1,i=0,len;

	next[0]=-1;

	len=strlen(s1);

	while(i<len)

	{

		if(j==-1||s1[i]==s1[j])

		{

			++i;

			++j;

			next[i]=j;

		}

		else

			j=next[j];

	}

}

int KMP(char s[],char s1[])

{

    int len,len1,i=0,j=0;

	len=strlen(s);

	len1=strlen(s1);

	while(i<len && j<len1)

	{

		if(j==-1||s[i]==s1[j])

		{

			++i;

			++j;

		}

		else

			j=next[j];

	}

	if(j>=len1)

		return i-len1+1;

	else

		return -1;

}

int main()

{

	int m;

	while(scanf("%s",s)!=EOF)//这里依照常理能够使用gets(s)!=NULL，可是在SDUTOJ上就是WR..所以仅仅能用scanf输入.

	{

		scanf("%s",s1);

		getnext(s1);

		m=KMP(s,s1);

		cout<<m<<endl;

	}

	return 0;

}