POJ 3080 Blue Jeans——暴力 + kmp

POJ 3080 Blue Jeans——暴力 + kmp

题意：找n个串都包含的最长连续子串，若子串的长度小于三输出no ，若有多个子串输出字典序最小的

思路：暴力枚举第一个串的全部连续子串（O（n^2）），然后用这个子串和其他字符串进行kmp

#include #include #include #include using namespace std;const int maxn = 100;char str[maxn][maxn], temp[maxn], ans[maxn];int T, n, Next[maxn];void makeNext(const char *p, int len) { int i = 0, j = 0; Next[i] = j; for (i = 1; i < len; i++) { while (j && p[i] != p[j]) j = Next[j - 1]; if (p[i] == p[j]) j++; Next[i] = j; }}bool kmp(const char *s, const char *p, int len) { makeNext(p, len); for (int i = 0, j = 0; i < 60; i++) { while (j && s[i] != p[j]) j = Next[j - 1]; if (s[i] == p[j]) j++; if (j == len) { return true; } } return false;}int main() { scanf("%d", &T); while (T--) { memset(ans, 0, sizeof(ans)); int len = 0; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%s", str[i]); } for (int i = 0; i < 60; i++) { for (int j = i; j < 60; j++) { int cnt = 0; for (int k = i; k <= j; k++) { temp[cnt++] = str[0][k]; } temp[cnt] = '\0'; bool ok = true; for (int k = 1; k < n; k++) { if (!kmp(str[k], temp, j - i + 1)) { ok = false; break; } } if (ok) { if ((len < j - i + 1) || (len == j - i + 1 && strcmp(ans, temp) > 0)) { len = j - i + 1; strcpy(ans, temp); } } } } if (len < 3) { printf("no significant commonalities\n"); } else { printf("%s\n", ans); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。