题解 CF1326D2 【Prefix-Suffix Palindrome (Hard version)】

恭喜你发现一只数据结构学傻了的 sb…… 先用字符串哈希正反求一遍，答案转换成一个位置开头/结尾，最长回文串，并且长度 $\le len$。 。。。 。。。 。。。 然后你发现你 manacher 忘了。。。 没事，还有回文树！ 正反建出回文树，在回文树上倍增即可。 时间 $\mathcal{O}(n\log n)$ ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1000005; const ll base=233; const ll mod1=998244353; const ll mod2=1e9+7; int n,k,ch[maxn][26],fa[maxn],len[maxn],pos[maxn],f[maxn][21],last,cnt; char s[maxn]; struct HASH { ll a,b; HASH(ll a_=0,ll b_=0):a(a_),b(b_) { } inline HASH rev() { return HASH((mod1-a)%mod1,(mod2-b)%mod2); } inline HASH operator * (const ll &x) { return HASH(a*x%mod1,b*x%mod2); } inline HASH operator * (const HASH &x) { return HASH(a*x.a%mod1,b*x.b%mod2); } inline HASH operator + (const HASH &x) { return HASH((a+x.a)%mod1,(b+x.b)%mod2); } inline bool operator == (const HASH &x) { return a==x.a && b==x.b; } }; HASH sum[2][maxn],b[maxn]; inline HASH get1(int l,int r) { return sum[0][r]+(sum[0][l-1]*b[r-l+1].rev()); } inline HASH get2(int l,int r) { return sum[1][l]+(sum[1][r+1]*b[r-l+1].rev()); } inline void chkmax(int &a,int b) { a=(a>b)?a:b; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%s",s+1); n=strlen(s+1); b[0]=HASH(1,1); for(int i=1;i<=n;i++) b[i]=b[i-1]*base,sum[0][i]=(sum[0][i-1]*base)+HASH(s[i],s[i]); sum[1][n+1]=HASH(0,0); for(int i=n;i;i--) sum[1][i]=(sum[1][i+1]*base)+HASH(s[i],s[i]); int res=0,l_=0,r_=n+1; s[0]='#',len[0]=0,len[1]=-1,fa[0]=1,cnt=1,last=0; int p,c,r,q; for(int i=1;i<=n;i++) { p=last,c=s[i]-'a'; while(s[i-len[p]-1]!=s[i]) p=fa[p]; if(!ch[p][c]) { r=++cnt,len[r]=len[p]+2,q=fa[p]; while(s[i-len[q]-1]!=s[i]) q=fa[q]; fa[r]=ch[q][c],ch[p][c]=r; } last=ch[p][c],pos[i]=last; } for(int i=0;i<=cnt;i++) f[i][0]=fa[i]; for(int j=1;j<=20;j++) for(int i=0;i<=cnt;i++) f[i][j]=f[f[i][j-1]][j-1]; for(int i=0;i<=n/2;i++) if(sum[0][i]==sum[1][n-i+1]) { int x=pos[n-i]; for(int j=20;j>=0;j--) if(f[x][j] && len[f[x][j]]>n-2*i) x=f[x][j]; if(len[x]>n-2*i) x=fa[x]; if(len[x]+2*i>res) res=len[x]+2*i,l_=i,r_=n-i+1-len[x]; } for(int i=0;i<=cnt;i++) { fa[i]=len[i]=pos[i]=0; memset(ch[i],0,sizeof(ch[i])); } last=cnt=0; reverse(s+1,s+n+1); s[0]='#',len[1]=-1,fa[0]=1,cnt=1,last=0; for(int i=1;i<=n;i++) { p=last,c=s[i]-'a'; while(s[i-len[p]-1]!=s[i]) p=fa[p]; if(!ch[p][c]) { r=++cnt,len[r]=len[p]+2,q=fa[p]; while(s[i-len[q]-1]!=s[i]) q=fa[q]; fa[r]=ch[q][c],ch[p][c]=r; } last=ch[p][c],pos[i]=last; } for(int i=0;i<=cnt;i++) f[i][0]=fa[i]; for(int j=1;j<=20;j++) for(int i=0;i<=cnt;i++) f[i][j]=f[f[i][j-1]][j-1]; for(int i=0;i<=n/2;i++) if(sum[0][i]==sum[1][n-i+1]) { int x=pos[n-i]; for(int j=20;j>=0;j--) if(f[x][j] && len[f[x][j]]>n-2*i) x=f[x][j]; if(len[x]>n-2*i) x=fa[x]; if(len[x]+2*i>res) res=len[x]+2*i,l_=i+len[x],r_=n-i+1; } reverse(s+1,s+n+1); for(int i=1;i<=l_;i++) putchar(s[i]); for(int i=r_;i<=n;i++) putchar(s[i]); putchar('\n'); for(int i=0;i<=cnt;i++) { fa[i]=len[i]=0; memset(ch[i],0,sizeof(ch[i])); } last=cnt=0; } return 0; } ```