Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

kmp+暴力枚举子串

Posted by zhouzp15 at 2017-01-18 21:57:14 on Problem 3080
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator