亲和串的定义是这样的:给定两个字符串s1和s2,如果能通过s1循环移位,使s2包含在s1中,那么我们就说s2 是s1的亲和串。
Input
Output
如果s2是s1的亲和串,则输出"yes",反之,输出"no"。每组测试的输出占一行。
Sample Input
AABCD
CDAA
ASD
ASDF
Sample Output
yes
no
哈哈哈 这个题 不解释 kmp模板的应用 ,详情请见我的kmp模板
#include<stdio.h>
#include<string.h>
#define N 110000
char s1[N+N],s2[N];
int next[N];
int kmp(char s1[],char s2[],int next[])
{
int i,j,k;
k = -1;
j = 0;
next[0] = -1;
while(s2[j]!='\0')
{
while(k!=-1&&s2[k]!=s2[j])
k = next[k];
j++;
k++;
if(s2[j] != s2[k])
next[j] = k;
else
next[j] = next[k];
}
j = i = 0;
while(s1[i]!='\0')
{
if(j != -1&&s2[j]=='\0')
{
j = 0;
return 1;
}
{
while(j != -1&&s1[i]!=s2[j])
j = next[j];
i++;
j++;
}
}
if(s2[j] =='\0')
return 1;
return 0;
}
int main()
{
int i,l;
while(scanf("%s",s1)!=EOF)
{
scanf("%s",s2);
l = strlen(s1);
for(i = l; i < l+l; i ++)//实现循环匹配
s1[i] = s1[i-l];
s1[i] = '\0';
if(kmp(s1,s2,next))
printf("yes\n");
else
printf("no\n");
}
return 0;
}