hdu 2203

Kmp初级应用，不解释

说一下失配函数的求解，其中的j其实既维护了改进前的next，又维护了改进后的next

//kmp
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
const int maxn=2*100000+10;
char s1[maxn],s2[maxn];
int nextv[maxn];
int len1,len2;
void getNext()
{
	int i=0,j=-1;
	nextv[0]=-1;
	while(i<len2-1)
	{
		if(j==-1||s2[i]==s2[j])
		{
			i++;
			j++;
			if(s2[i]==s2[j]) nextv[i]=nextv[j];
			else nextv[i]=j;
		}
		else j=nextv[j];
	}
}
int main()
{
	while(gets(s1))
	{
		gets(s2);
		int tem=0;
		int i,j;
		len1=strlen(s1);len2=strlen(s2);
		for(i=0,j=len1;i<len1-1;i++,j++) s1[j]=s1[i];
		len1=2*len1-1;
		i=-1,j=-1;
		getNext();
		while(i<len1&&j<len2)
		{
			if(j==-1||s1[i]==s2[j])
			{
				i++;
				j++;
			}
			else j=nextv[j];
		}
		if(j==len2) printf("yes\n");
		else printf("no\n"); 
	}
	return 0;
}