| ||||||||||
| 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