| ||||||||||
| 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 | |||||||||
贴个代码#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator