发布于2018年8月17日2018年8月19日 由itewqq[KMP][二分] POJ 3450 这个题有很多做法，目前先用二分+KMP过了，二分的原理是如果最大字串存在那么这个最大字串的字串也一定满足要求。难得1Y，明天用后缀数组尝试一下来填坑。。 //#include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include #define eps (1e-6) using namespace std; typedef long long LL; const int maxn=2e2+5; const int MOD=1e9+7; const int INF=0x4f4f4f4f; char y[4005][maxn],ma[maxn]; int nxt[maxn]; void kmp_pre(char * x,int m) { int i,j; j=nxt[0]=-1; i=0; while(i=m) { return 1; } } return 0; } int t,l,r,tl,tmp,flag=0,mid,len[4005]; char tep[maxn]; int check(int k) { int ans; ans=1; for (int i=0; i+k<=tl; i++) { char *x=ma+i; int j; for (j=1; j<=t; j++) { if(!KMP_Count(x,k,j,len[j])) break; } if(j>t) return 1; } return 0; } char ans[maxn],fuck[maxn]; void getans(int k) { int flag=-1; ans[0]='z'+1; char * x; for (int i=0; i+k<=tl; i++) { x=i+ma; int j; for (j=1; j<=t; j++) { if(!KMP_Count(x,k,j,len[j])) break; } if(j>t) { strcpy(fuck,x); fuck[k]=0; if(strcmp(fuck,ans)<0) { strcpy(ans,fuck); } } } printf("%s\n",ans); } int main() { //freopen("1.txt","r",stdin); //freopen("2.txt","w",stdout); while(~scanf("%d",&t)&&t) { tl=INF; flag=0; getchar(); for (int i=1; i<=t; i++) { gets(y[i]); len[i]=strlen(y[i]); if(len[i]l) { mid=(r+l+1)>>1; if(check(mid)) l=mid; else r=mid-1; } if(r!=0) getans(r); else printf("IDENTITY LOST\n"); } return 0; }
