题解 CF1326D2 【Prefix-Suffix Palindrome (Hard version)】
Owen_codeisking
2020-08-27 16:24:07
恭喜你发现一只数据结构学傻了的 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;
}
```