亲和串

Problem Description

人随着岁数的增长是越大越聪明还是越大越笨，这是一个值得全世界科学家思考的问题,同样的问题Eddy也一直在思考，因为他在很小的时候就知道亲和串如何判断了，但是发现，现在长大了却不知道怎么去判断亲和串了，于是他只好又再一次来请教聪明且乐于助人的你来解决这个问题。
亲和串的定义是这样的：给定两个字符串s1和s2,如果能通过s1循环移位，使s2包含在s1中，那么我们就说s2 是s1的亲和串。

Input

本题有多组测试数据，每组数据的第一行包含输入字符串s1,第二行包含输入字符串s2，s1与s2的长度均小于100000。

Output

如果s2是s1的亲和串，则输出"yes"，反之，输出"no"。每组测试的输出占一行。

Sample Input

AABCD

CDAA

ASD

ASDF

Sample Output

yes

no

题意描述：
判断两个字符串s1,s2是否满足s1通过循环移位包含s2.

解题思路：

利用kmp当循环查找当查到相同时标记，跳出循环；当i=lena时即i将主串走过一遍后，i=0从头继续查找实现循环移位，当第二遍i又找到lena时结束跳出循环，若还没有出现子串，输出no;

#include<stdio.h>
#include<string.h>
int main()
{
	char a[100010],b[100010];
	int lena,lenb,i,j,next[100010],flag,h;
	while(gets(a)!=NULL)
	{
		gets(b);
		lena=strlen(a);
		lenb=strlen(b);
		j=0;
		next[0]=0;
		//求出b的next[]数组 
		for(i=1;i<=lenb-1;)
		{
			if(j==0&&b[i]!=b[j])
			{
				next[i]=0;
				i++;
			}
			if(b[i]==b[j])
			{
				next[i]=j+1;	
				i++;
				j++;
			}
			if(j>0&&b[i]!=b[j])
			{
				j=next[j-1];
			}
		}
		flag=0;
		h=0;
		for(i=0,j=0;;)
		{
			if(a[i]==b[j])
			{
				j++;
				if(j==lenb)
				{
					flag=1;
					break;
				}
				i++;
			}
			if(h==1&&i==lena)//第二次又查找完时，结束循环 
				break;
			
			if(h==0&&i==lena)//当第一次字符串a查完时，i变为0 
			{
				i=0;
				h=1;
			}
			
			if(j==0&&a[i]!=b[j])
				i++;
				
			//因在循环中又两个i++,在哪个后边查找完都有可能所以判断了两次 
			if(h==0&&i==lena)//当第一次字符串a查完时，i变为0 
			{
				i=0;
				h=1;
			}
			if(j>0&&a[i]!=b[j])
				j=next[j-1];
		}
		if(flag==1)
			printf("yes\n");
		else
			printf("no\n");
	}
}