hdu2203——亲和串

题意：判断s2是否是s1的亲和串。

思路：将s1接在s1后面，然后作kmp判断。

#include<iostream>
using namespace std ;
char s1[100002*2],s2[100003];
int next[100002*2];
void getnext(char s[],int next[])
{
	next[0]=-1;
	int j=-1;
	int len1=strlen(s);
	for(int i=1;i<len1;i++)
	{
		while(j>-1&&s[j+1]!=s[i])
			j=next[j];
		if(s[j+1]==s[i])
			j++;
		next[i]=j;
	}
}
int  solve(int l1,int l2)
{
	int i=0,j=0;
	while(i<l1&&j<l2)
	{
		if(s1[i]==s2[j])
		{ i++;j++;}
		else if(j==0) i++;
		else j=next[j-1]+1;
	}
	if(j==l2) return 1;
	else return -1;
}
int main()
{
	while(gets(s1)!=NULL)
	{
		gets(s2);
		int i,j,l=strlen(s1),l2=strlen(s2);
		if(l<l2)
		cout<<"no"<<endl;
		else {
		for(j=l,i=0;i<l;i++)
		{
			s1[j+i]=s1[i];
		}
		s1[2*l-1]='\0';
		getnext(s1,next);
		int t=solve(2*l,l2);
		if(t==-1) cout<<"no"<<endl;
		else cout<<"yes"<<endl;
		}
	}
	return 0;
}