这道题可以$O(nlogn)$,当然也可以$O(n)$做啦$qwq$
$O(nlogn)$的思路是枚举每个回文中心,通过哈希预处理出前缀和后缀哈希值备用,然后二分回文串的长度,具体的就是判断在长度范围内,前缀哈希值和后缀哈希值是否相等。
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cctype> #include<cstdlib> #include<vector> #include<queue> #include<map> #include<set> #define ll unsigned long long #define R register int using namespace std; namespace Fread { static char B[1<<15],*S=B,*D=B; #define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++) inline int g() { R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix; } }using Fread::g; const int B=131,N=1000010; int t,ans; ll h1[N],h2[N],p[N]; char s[N]; inline ll H1(int l,int r) {return h1[r]-h1[l-1]*p[r-l+1];} inline ll H2(int l,int r) {return h2[l]-h2[r+1]*p[r-l+1];} signed main() { #ifdef JACK freopen("NOIPAK++.in","r",stdin); #endif p[0]=1; for(R i=1;i<=N-10;++i) p[i]=p[i-1]*B; while(1) { ans=0; ++t; scanf("%s",s+1); R len=strlen(s+1); if(len==3&&s[1]=='E'&&s[2]=='N'&&s[3]=='D') break; for(R i=1;i<=len;++i) h1[i]=h1[i-1]*B+(s[i]^48)+1; for(R i=len;i>=1;--i) h2[i]=h2[i+1]*B+(s[i]^48)+1; for(R p=1;p<=len;++p) { register int l=1,r=min(p-1,len-p); while(l<r) { register int md=l+r+1>>1; if(H1(p-md,p-1)==H2(p+1,p+md)) l=md; else r=md-1; } ans=max(ans,l*2+1); l=1,r=min(p-1,len-p+1); while(l<r) { register int md=l+r+1>>1; if(H1(p-md,p-1)==H2(p,p+md-1)) l=md; else r=md-1; } ans=max(ans,l*2); } printf("Case %d: %d\n",t,ans); } }
还有一个$Manacher$算法,可以在$O(n)$时间里解决这个问题,详见这位大佬的博客
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<cctype> #include<cstdlib> #include<vector> #include<queue> #include<map> #include<set> #define ll long long #define R register int using namespace std; namespace Fread { static char B[1<<15],*S=B,*D=B; #define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++) inline int g() { R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix; } }using Fread::g; const int N=1000010; char s[N<<1],str[N<<1]; int len[N<<1],l; inline void getstr() { R k=0; str[k]='$'; for(R i=0;i<=l;++i) str[++k]='#',str[++k]=s[i]; str[++k]='#'; l=k; } inline void Manacher() { getstr(); R mx=0,id; for(R i=1;i<l;++i) { if(mx>i) len[i]=min(len[2*id-i],mx-i);//先找对称的位置,和右边界取一个min else len[i]=1;//不包含直接设为1 while(str[i+len[i]]==str[i-len[i]]) ++len[i];//暴力匹配 if(len[i]+i>mx) mx=len[i]+i,id=i;//更新mx和id } } signed main() { #ifdef JACK freopen("NOIPAK++.in","r",stdin); #endif R t=0; while(1) { memset(len,0,sizeof(len)); ++t; scanf("%s",s); l=strlen(s); if(l==3&&s[0]=='E'&&s[1]=='N'&&s[2]=='D') break; Manacher(); R ans=1; for(R i=1;i<l;++i) ans=max(ans,len[i]); printf("Case %d: %d\n",t,ans-1); } }
洛谷上也有$manacher$的模板,可以水一下;
2019.06.10