本文主要是介绍hdu 4300 Clairewd’s message （KMP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：http://acm.hdu.edu.cn/showproblem.php?pid=4300
第一个串给定密文的翻译方式，然后去求一个暗文+明文正确格式的串。
思路：保存一个翻译好的明文串，然后和暗文去匹配，从暗文的一半开始匹配，匹配到末看匹配了几个，n - 个数就是暗文/明文的长度
代码：
#include <stdio.h>
#include <string.h>const int N = 100005;char tr[30], tra[30], s1[N], s2[N];
int next[N], n, t, i;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;}
}int kmp(char *seq, char *seq1, int n, int m) {int j = next[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 (i == n - 1) {return j + 1;}}return false;
}int main() {scanf("%d", &t);while (t--) {scanf("%s%s", tr, s1);for (i = 0; i < 26; i++)tra[tr[i] - 'a'] = i + 'a';n = strlen(s1); s2[n] = '\0';for (i = 0; i < n; i++)s2[i] = tra[s1[i] - 'a'];get_next(s2, n);int k = n - kmp(s1 + (n + 1) / 2, s2, strlen(s1 + (n + 1) / 2), n);for (i = 0; i < k; i++)printf("%c", s1[i]);for (i = 0; i < k; i++)printf("%c", s2[i]);printf("\n");}return 0;
}
这篇关于hdu 4300 Clairewd’s message （KMP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
