hdu 1238 Substrings（KMP）

本文主要是介绍hdu 1238 Substrings（KMP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1238

求个公共字串，正逆序其中一个满足即可。

KMP暴力即可。判断的时候正逆序都去判断即可

代码：

#include <stdio.h>
#include <string.h>const int N = 105;
#define max(a,b) ((a)>(b)?(a):(b))
char s[N][N], rs[N][N];
int next[N], n, t;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 judge(char *seq1) {for (int i = 1; i < n; i++) {if (!kmp(s[i], seq1, strlen(s[i]), strlen(seq1)) && !kmp(rs[i], seq1, strlen(rs[i]), strlen(seq1)))return false;}return true;
}void solve() {int ans = 0;int len = strlen(s[0]);char s2[N];for (int i = 0; i < len; i++) {get_next(s[0] + i, len - i);memset(s2, 0, sizeof(s2)); int s2n = 0;for (int j = i; j < len; j++) {s2[s2n++] = s[0][j];if (judge(s2))ans = max(s2n, ans);}}printf("%d\n", ans);
}int main() {scanf("%d", &t);while (t--) {memset(rs, 0, sizeof(rs));scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%s", s[i]);int len = strlen(s[i]);for (int j = len - 1; j >= 0; j--)rs[i][len - j - 1] = s[i][j];}solve();}return 0;
}

这篇关于hdu 1238 Substrings（KMP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---