亲和串
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4204 Accepted Submission(s): 1912
Problem Description
人随着岁数的增长是越大越聪明还是越大越笨，这是一个值得全世界科学家思考的问题,同样的问题Eddy也一直在思考，因为他在很小的时候就知道亲和串如何判断了，但是发现，现在长大了却不知道怎么去判断亲和串了，于是他只好又再一次来请教聪明且乐于助人的你来解决这个问题。
亲和串的定义是这样的：给定两个字符串s1和s2,如果能通过s1循环移位，使s2包含在s1中，那么我们就说s2 是s1的亲和串。
亲和串的定义是这样的：给定两个字符串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
Author
Eddy
Recommend
lcy
题解：这题是字符串匹配的简单题 简单使用KMP算法模板或者AC自动机模板就能够A 起初还是怀疑string类型存储的字符有限
上网查了一下发现string类型所存储的字符是无尽的 这题我用的是KMP算法做的 主要考虑循环 就是两个母串首尾相连 就能够
解决这个问题 剩下的就是字符串匹配了 按照构造next数组KMP的模板 就能轻松A 题意没有叙述清楚子串能不能比母串长
所以这
里我有优化就是当母串小于子串 直接输出 不做匹配 实际上确实是这样 详细见代码
#include <iostream>
#include<cstring>
#include<cstdio>
using namespace std;
string s0,s1,s2;
int next[200005];
void get_next(const string sub, int *next)
{
int len=sub.length();
int i,k;
next[0]=k=-1;
for (i=0; i<len;)
{
if (k==-1 || sub[i]==sub[k])
{
k++;
i++;
if (sub[k]!=sub[i]) next[i]=k;
else next[i]=next[k]; //避免重复计算优化next数组
}
else k=next[k];
}
}
int KMP(const string str, const string sub, const int *next) //返回子串在主串中的起始位置下标
{
int i,j;
int len1=str.length();
int len2=sub.length();
for (i=0, j=0; i<len1 && j<len2;)
{
if (j==-1 || str[i]==sub[j])
{
i++;
j++;
}
else
{
j=next[j];
}
}
if (j==len2) return i-len2;
return -1; //如果找不到就返回-1
}
int main()
{
while(cin>>s0>>s2)
{
if(s2.length()>s0.length())
{
cout<<"no"<<endl;
}
else
{
s1=s0+s0;
get_next(s2,next);
int ans=KMP(s1,s2,next);
// cout<<ans<<endl;
if(ans==-1)
cout<<"no"<<endl;
else
cout<<"yes"<<endl;
}
}
return 0;
}
