| ||||||||||
| 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 | |||||||||
why wa?#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator