本文主要是介绍HDU 2023 亲和串（KMP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
亲和串
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 6954 Accepted Submission(s): 3156
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
先判断长度是否合适，然后把第一个串存成两倍去进行KMP即可
代码：
#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f
const int N = 200005;char s1[N], s2[N];
int next[N], t, n;void get_next(char *seq, int m) {next[0] = -1;int j = next[0];for (int i = 1; i < m; i++) {while (j >= 0 && seq[i] != seq[j + 1]) j = next[j];if (seq[i] == seq[j + 1]) j++;next[i] = j;}
}bool kmp(char *seq, char *seq1, int n, int m) {int j = next[0], ans = 0;for (int i = 0; i < n; i++) {while (j >= 0 && seq[i] != seq1[j + 1]) j = next[j];if (seq[i] == seq1[j + 1]) j++;if (j == m - 1)return true;}return false;
}bool solve() {int len1 = strlen(s1), len2 = strlen(s2);if (len1 < len2) return false;for (int i = len1; i < len1 * 2; i++)s1[i] = s1[i - len1];s1[len1 * 2] = '\0'; len1 = len1 * 2;get_next(s2, len2);return kmp(s1, s2, len1, len2);
}int main() {while (~scanf("%s%s", s1, s2)) {printf("%s\n", solve()?"yes":"no");}return 0;
}这篇关于HDU 2023 亲和串（KMP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
