Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
kmp+暴力枚举子串#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; const int LEN = 60; const int N = 10 + 2; const int M = LEN + 2; int next[M], n, len; char dna[N][M]; bool kmp(const char *T, const char *P) { int t = next[0] = -1, j = 0; int lenT = strlen(T), lenP = strlen(P); while (j < lenP - 1) if (t < 0 || P[t] == P[j]) t++, j++, next[j] = (P[j] == P[t] ? next[t] : t); else t = next[t]; int i = 0; j = 0; while (i < lenT && j < lenP) if (j < 0 || T[i] == P[j]) i++, j++; else j = next[j]; return j == lenP; } bool match(const char *substr) { for (int i = 1; i < n; i++) if ( !kmp(dna[i], substr) ) return false; return true; } int main() { int T; scanf("%d", &T); char ans[M], tmp[M]; while (T--) { scanf("%d\n", &n); for (int i = 0; i < n; i++) gets(dna[i]); bool flag = false; for (len = LEN; len > 0; len--) { for (int pos = 0; pos <= LEN - len; pos++) { strncpy(tmp, dna[0] + pos, len); tmp[len] = '\0'; if ( match(tmp) ) { if (!flag || strcmp(tmp, ans) < 0) strcpy(ans, tmp); flag = true; } } if (flag) break; } if (len < 3) printf("no significant commonalities\n"); else printf("%s\n", ans); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator