题目链接: hdu 4763
题目大意: 找出字符串的最长子串,这个子串满足既是前缀和后缀,并且在中间会出现
解题思路: 不妨先找出所有前缀等于后缀的子串长度(poj 2752 解题报告)
从长到短(长度不大于主串的1/3)枚举子串的长度
前缀等于后缀的子串长度为ans[ i ]
根据next[ ]的性质,中间再次出现这个串的话,那么next[ ]数组的值必会等于ans[ i ]
中间会出现长度依然等于ans[ i ]的子串的nex[ ]t区间必定在[2*ans[ i ],Tlen-ans[ i ]]
代码:
//Final KMP变形,poj 2752升级版,找出所有字符串的最长子串,这个子串满足既是前缀又是后缀,并且中间也出现(不可以重叠) #include <stdio.h> #include <string.h> #define MAX 1000010 char ch[MAX]; int Tlen,next[MAX],ans[MAX]; void Get_next() //求字符串的next[]前缀数组 { int i=0,j=-1; next[0]=-1; while(i<Tlen) { if(j==-1||ch[i]==ch[j]) { i++; j++; next[i]=j; } else j=next[j]; } } int main() { int i,j,n,k,kk,pd,t; scanf("%d",&t); while(t--) { scanf("%s",ch); Tlen=strlen(ch); memset(next,0,sizeof(next)); Get_next(); ans[0]=Tlen; //本身也是 n=0; i=Tlen; while(next[i]>0) //根据next[]性质求出所有满足题意的长度 { ans[++n]=next[i]; i=next[i]; } k=Tlen/3; //子串的长度最长是主串的1/3 pd=0; for(i=0;i<=n;i++) //子串长度从长到短枚举 { if(ans[i]>k) //子串的长度必定会小于或等于Tlen/3 continue; else { kk=Tlen-ans[i]; for(j=ans[i]+ans[i];j<=kk;j++) //根据next[]的性质从区间[2*ans[i],Tlen-ans[i]]寻找 { if(next[j]==ans[i]) { pd=1; break; } } } if(pd==1) { printf("%d\n",ans[i]); break; } } if(pd==0) printf("%d\n",0); } return 0; }