|
Posted on 2009-10-13 22:46 Uriel 阅读(839) 评论(0) 编辑 收藏 引用 所属分类: POJ 、 字符串处理
后缀数组还是没懂。。 Regional之前应该是来不及了。。 这题可以练后缀数组的。。 KMP水过去了。。后来发现 strstr也行。。跟KMP一样16Ms。。。 strstr版本:
/**//*Problem: 3080 User: Uriel Memory: 584K Time: 16MS Language: G++ Result: Accepted*/
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm>
using namespace std;
int start,n; char str[15][100];
struct P { char res[100]; }Ans[100];
char dest[100]; int Next[100];
bool cmp(P a,P b) { return strcmp(a.res,b.res)<0; }
void Sov() { int i; for(i=1;i<n;i++) { if(strstr(str[i],dest)==NULL) { start=1; return ; } } return ; }
int main() { int t,i,j,k,s; scanf("%d",&t); while(t--) { scanf("%d",&n); memset(str,0x00,sizeof(str)); for(i=0;i<n;i++) { scanf("%s",str[i]); } s=0; for(i=60;i>=3;i--) { j=0; while(j+i<=60) { start=0; memset(dest,0x00,sizeof(dest)); strncpy(dest,&str[0][j],i); Sov(); if(!start) { strcpy(Ans[s++].res,dest); } j++; } if(s)break; } if(s) { sort(Ans,Ans+s,cmp); printf("%s\n",Ans[0].res); } else { printf("no significant commonalities\n"); } } return 0; }
KMP版本:
/**//*Problem: 3080 User: Gilhirith Memory: 584K Time: 16MS Language: G++ Result: Accepted*/
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm>
using namespace std;
int start,n; char str[15][100]; char dest[100]; int Next[100];
struct P { char res[100]; }Ans[100];
int GetNextVal(char* Pattern, int next[]) { int i=1,j=0; int p_len=strlen(Pattern); next[0]=0; while(i<p_len) { if(Pattern[i]==Pattern[j]) { next[i]=j+1; i++; j++; } else if(j>0) { j=next[j-1]; } else { next[i]=0; i++; } } return 0; }
int kmpMatch(char* Src, char* Pattern, int pos) { int i=pos,j=0; int s_len,p_len; s_len=strlen(Src); p_len=strlen(Pattern); while(i<s_len) { if(Src[i]==Pattern[j]) { if(j==p_len-1)return i-p_len+1; i++; j++; } else if(j>0) { j=Next[j-1]; } else i++; } return -1; }
bool cmp(P a,P b) { return strcmp(a.res,b.res)<0; }
void Sov() { int i; for(i=1;i<n;i++) { if(kmpMatch(str[i], dest, 0)==-1) { start=1; return ; } } return ; }
int main() { int t,i,j,k,s; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=0;i<n;i++) { scanf("%s",str[i]); } s=0; for(i=60;i>=3;i--) { j=0; while(j+i<=60) { start=0; memset(dest,0x00,sizeof(dest)); strncpy(dest,&str[0][j],i); GetNextVal(dest,Next); Sov(); if(!start) { strcpy(Ans[s++].res,dest); } j++; } if(s)break; } if(s) { sort(Ans,Ans+s,cmp); printf("%s\n",Ans[0].res); } else { printf("no significant commonalities\n"); } } return 0; }
|