hdu 2203 亲和串 (KMP算法)

http://acm.hdu.edu.cn/showproblem.php?pid=2203

 

解题报告：由题目：给定两个字符串s1和s2,如果能通过s1循环移位，使s2包含在s1中，那么我们就说s2 是s1的亲和串。移位循环，最多多循环循环一个s1的长度，因此我们可以把s1中的前n-1位直接添加到s1的后面，

如s1=AABCD,可以变为s1=AABCDAABC，这样就包含了所有的情况，然后循环遍历即可。

 

 

#include<cstdio>
#include<cstring>

using namespace std;

const int MAX = 100000 + 5;
char a[2*MAX],b[MAX];
int next[MAX],len1,len2;

void get_next()
{
	int i,j=-1;
	next[0]=-1;
	for(int i=1;i<=len2;i++)
	{
		while(j>-1&&b[j+1]!=b[i])
		{
			j=next[j];
		}
		if(b[j+1]==b[i])
			j++;
		next[i]=j;
	}
}

bool KMP()
{
	get_next();
	int i=0,j=-1;
	for(int i=0;i<2*len1-1;i++)
	{
		while(j>-1&&b[j+1]!=a[i])
			j=next[j];
		if(b[j+1]==a[i])
			j++;
		if(j==len2-1)
			return true;
	}
	return false;
}

int main()
{
	while(scanf("%s %s",a,b)!=EOF)
	{
		
		len1=strlen(a);
		for(int j=0;j<len1-1;j++)
			a[j+len1]=a[j];
		len2=strlen(b);
		if(KMP()) printf("yes\n");
		else printf("no\n");
	}
	return 0;
}