首页 > 代码库 > hdu2203--亲和串
hdu2203--亲和串
亲和串
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 8523 Accepted Submission(s): 3893
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 | We have carefully selected several similar problems for you: 2201 3068 2202 2200 2206
把环展开成链,然后kmp匹配一下就行
把环展开成链,然后kmp匹配一下就行
/************************************************************************* > File Name: hdu2203.cpp > Author: ALex > Mail: 405045132@qq.com > Created Time: 2015年01月05日 星期一 11时06分38秒 ************************************************************************/ #include <map> #include <set> #include <queue> #include <stack> #include <vector> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 100010; int next[N]; char str[N]; char text[N << 1]; void get_next() { int len = strlen(str); int j = 0; int k = -1; next[0] = -1; while (j < len) { if (k == -1 || str[j] == str[k]) { next[++j] = ++k; } else { k = next[k]; } } } bool KMP() { int len1 = strlen(text); int len2 = strlen(str); int i = 0; int j = 0; while (j < len2 && i < len1) { if (j == -1 || str[j] == text[i]) { ++i; ++j; } else { j = next[j]; } } if (j == len2) { return 1; } return 0; } int main() { while (~scanf("%s%s", text, str)) { get_next(); int len = strlen(text); for (int i = len; i < 2 * len - 1; ++i) { text[i] = text[i - len]; } text[2 * len - 1] = '\0'; if (KMP()) { printf("yes\n"); } else { printf("no\n"); } } return 0; }
hdu2203--亲和串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。