亲和串
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2486 Accepted Submission(s): 1116
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
Author
Eddy
#include <iostream>
using namespace std;
const int _N = 100005;
char s1[_N], s2[_N], s[_N << 1];
int next[_N];
//亲和串的定义是这样的:给定两个字符串s1和s2,如果能通过s1循环移位,使s2包含在s1中,那么我们就说s2 是s1的亲和串。
//算法思路:由于是循环移位,则我们可以把s1和s1连接起来,如例子所示:
//AABCD AABCD
//DAABC
//CDAAB
//BCDAA
//ABCDA
//AABCD
//循环移位后的字串都能在连接后的串中找到,用kmp搞定
void getNext()
{
int i = 0, j = -1;
int len = strlen(s2);
next[0] = -1;
while(i < len)
{
if(j == -1 || s2[i] == s2[j])
{
i++;j++;
if(s2[i] == s2[j])
next[i] = next[j];
else
next[i] = j;
}else
j = next[j];
}
}
void kmp()
{
getNext();
int slen = strlen(s);
int len = strlen(s2);
int i = 0, j = 0;
while(i < slen && j < len)
{
if(j == -1 || s[i] == s2[j])
{
i++; j++;
}else
j = next[j];
}
if(j == len)
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
int main()
{
while(cin>>s1>>s2)
{
strcpy(s, s1);
strcat(s, s1);
kmp();
}
return 0;
}
分享到:
相关推荐
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu1290 解题报告 献给杭电五十周年校庆的礼物 (切西瓜问题,即平面分割空间)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
HDU图论题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码