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

贴个代码

Posted by tcet030840zxp at 2011-12-13 12:15:32 on Problem 3080
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
vector<string>ans;
char b[65];
int	pai[65];
char s[12][65];
int lena,lenb;
void compute(char b[])
{
	int k=0;
	pai[1]=0;
	for(int q=2;q<=lenb;q++)
	{
		while(k>0&&b[k+1]!=b[q])k=pai[k];
		if(b[k+1]==b[q])k+=1;
		pai[q]=k;
	}
}
int kmp(char a[],char b[])
{
	compute(b);
	int i,q=0;
	for(i=1;i<=lena;i++)
	{
		while(q>0&&b[q+1]!=a[i])q=pai[q];
		if(b[q+1]==a[i])q+=1;
		if(q==lenb)return 1;
	}
	return 0;
}
bool cmp(const string &a,const string &b)
{
	return a.size()>b.size();
}
int main()
{
	int i,j,k,T,t;
	scanf("%d",&T);
	while(T--)
	{
		ans.clear();
		bool leap=true;
		scanf("%d",&t);
		for(i=0;i<t;i++)
		{
			s[i][0]='0';
			scanf("%s",s[i]+1);
			if(strlen(s[i])<=3)
			{
				leap=false;
				break;
			}
		}
		if(!leap)continue;
		int length=strlen(s[0])-1;
		for(i=1;i<=length-2;i++)
		{
			for(j=i+2;j<=length;j++)
			{
				memset(b,0,sizeof(b));b[0]='A';
				for(k=i;k<=j;k++)b[k-i+1]=s[0][k];
				lenb=j-i+1;
				for(k=1;k<t;k++)
				{
					lena=strlen(s[k])-1;
					if(!kmp(s[k],b))break;
				}
				if(k==t)ans.push_back(string(b+1));
			}
		}
		if(ans.size()==0)printf("no significant commonalities\n");
		else
		{
			sort(ans.begin(),ans.end());
			stable_sort(ans.begin(),ans.end(),cmp);
			cout<<ans[0]<<endl;
		}
	}
	//system("pause");
	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