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

why wa?

Posted by Acaini at 2009-07-30 19:48:40 on Problem 3080 and last updated at 2009-07-30 19:50:24
#include<iostream>
#include<string>
using namespace std;
#define M 1000
#define L 60
//int kmp(char *t,char *p,int pos)
int kmp(char *t,char *p)
{
	//p模式串,t主串
	//预处理
	int next[M];
	//memset(next,0,sizeof(next));
	int  i,j,
		lent=strlen(t),
		lenp=strlen(p);
	next[0]=-1;
	i=0;j=-1;
	while(i<lenp-1)
		if(j==-1 || p[i]==p[j])
		{
			++i;++j;
			if(p[i]!=p[j]) next[i]=j;
			else next[i]=next[j];
			//next[i]=j;
		}
		else j=next[j];
	//匹配
	i=0;j=0;
	while(i<lent && j<lenp)
		if(j==-1 || t[i]==p[j]) {++i;++j;}
		else j=next[j];

	if(j==lenp) return i-lenp;
	else return -1;
}

int main()
{
	char s[11][61], p[61],res[61];
	int c,n,i,j,k,m;
	bool flag1,flag2;
	scanf("%d",&c);
	while(c--)
	{
		scanf("%d",&n);
		for(i=0;i<n;i++)
			scanf(" %s",&s[i]);
		memset(res,'z',sizeof(res));
		res[60]=0;
		for(i=L;i>=3;i--)//字串长,从大搜到小
		{
			flag1=false; //该长度是否能匹配到
			for(j=0;i+j<L;j++)//逐个
			{
				flag2=true;
				for(k=0;k<i;k++)
					p[k]=s[0][j+k];
				p[k]=0;

				for(m=1;m<n;m++)//在其他串中检索
					if(kmp(s[m],p)==-1) 
					{
						flag2=false; 
						break;
					}
				if(flag2) 
				{
					flag1=true;
					if(strcmp(p,res)<0) strcpy(res,p);
				}
			}// for j
			if(flag1) 
			{
				printf("%s\n",res);
				break;
			}
		}// for i
		if(i<3) printf("no significant commonalities\n");
	}
	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