首页 > 代码库 > NYOJ327 亲和串 【KMP】
NYOJ327 亲和串 【KMP】
亲和串
时间限制:1000 ms | 内存限制:65535 KB
难度:3
- 描述
- 最近zyc遇到了一个很棘手的问题:判断亲和串,以前判断亲和串的时候直接可以看出来,但现在不同了,现在给出的两字符串都非常的大,看的zyc头都晕了。于是zyc希望大家能帮他想一个办法来快速判断亲和串。亲和串定义:给定两个字符串s1和s2,如果能通过s1循环移动,使s2包含在s1中,那么我们就说s2是s1的亲和串。
- 输入
- 本题有多组测试数据,每组数据的第一行包含输入字符串s1,第二行包含输入字符串s2,s1与s2的长度均小于100000。
- 输出
- 如果s2是s1的亲和串,则输出"yes",反之,输出"no"。每组测试的输出占一行。
- 样例输入
AABCD CDAA ASD ASDF
- 样例输出
yes no
#include <stdio.h> #include <string.h> #define maxn 100000 + 5 char str1[2 * maxn], str2[maxn]; int next[maxn], len1, len2;; void getNext(){ int j = -1, i = 0; next[0] = -1; while(i < len2){ if(j == -1 || str2[i] == str2[j]){ ++i; ++j; if(str2[i] != str2[j]) next[i] = j; else next[i] = next[j]; }else j = next[j]; } } bool KMP(){ getNext(); int i = 0, j = 0; while(i < len1 && j < len2){ if(j == -1 || str1[i] == str2[j]) ++j, ++i; else j = next[j]; } return j == len2; } int main(){ while(scanf("%s%s", str1, str2) == 2){ len1 = strlen(str1); len2 = strlen(str2); if(len1 < len2){ printf("no\n"); continue; } memcpy(str1 + len1, str1, len1); len1 *= 2; if(KMP()) printf("yes\n"); else printf("no\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。