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