【BZOJ4166】月宫的符卡序列
题解：题倒不难，就是有点恶心。
首先学习回文串的时候一定学到了这样一个结论：一个长度为n的串的本质不同的回文子串数量不超过n个。
那么我们就可以试图将所有回文串的价值都计算出来，这就需要我们先计算出每个回文中心i的最长回文半径rl[i]，那么那些半径在[1,rl[i]]中的，且以i为回文中心的回文串的价值都应该被更新。其实只需要更新最长的那个就行，其余的可以扫一遍回文树，逐层更新上去。但是回文树太大建不出来怎么办？我们可以用hash，直接通过hash值得到每个串在回文树上的父亲。这样就可以更新了。
但是hash要用到map啊，然后本人就被光荣的卡常了。于是采取了一点黑科技~
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn=2000010;
vector<int> v[maxn];
const ll m1=9997957;
const ll m2=1000000007;
int n,tot,len,ml,pos,mx;
char str[maxn],ss[maxn];
int rl[maxn],ans[maxn],p[maxn];
int head[10000000],next[maxn];
ll h1[maxn],b1[maxn],h2[maxn],b2[maxn],val[maxn];
int find(ll t1,ll t2)
{
for(int i=head[t1];i;i=next[i]) if(val[i]==t2) return i;
return 0;
}
void add(ll t1,ll t2)
{
val[++tot]=t2,next[tot]=head[t1],head[t1]=tot;
}
void work()
{
n=tot=mx=0;
memset(ans,0,sizeof(ans));
memset(rl,0,sizeof(rl));
memset(head,0,sizeof(head));
scanf("%s",ss),len=strlen(ss);
int i,j,k,t;
ll t1,t2;
str[n++]='*';
for(i=0;i<len;i++) str[n++]=ss[i],str[n++]='*';
for(ml=-1,i=0;i<n;i++)
{
if(i<ml) rl[i]=min(ml-i+1,rl[2*pos-i]);
else rl[i]=1;
for(;rl[i]<=i&&i+rl[i]<n&&str[i+rl[i]]==str[i-rl[i]];rl[i]++);
if(i+rl[i]-1>ml) pos=i,ml=i+rl[i]-1;
}
for(b1[0]=b2[0]=1,i=1;i<=n;i++) b1[i]=b1[i-1]*233%m1,b2[i]=b2[i-1]*2333%m2;
for(i=0;i<n;i++)
{
if(i) h1[i]=h1[i-1]*233%m1,h2[i]=h2[i-1]*2333%m2;
h1[i]=(h1[i]+str[i])%m1,h2[i]=(h2[i]+str[i])%m2;
}
for(i=0;i<n;i++)
{
if(rl[i]==1) continue;
t1=(h1[i+rl[i]-1]-h1[i-1]*b1[rl[i]]%m1+m1)%m1;
t2=(h2[i+rl[i]-1]-h2[i-1]*b2[rl[i]]%m2+m2)%m2;
t=find(t1,t2);
if(t)
{
ans[t]^=(i-1>>1);
continue;
}
add(t1,t2),ans[tot]=(i-1>>1),p[tot]=i,v[rl[i]-1].push_back(tot);
}
for(i=len;i;i--)
{
for(j=0;j<v[i].size();j++)
{
k=v[i][j],mx=max(mx,ans[k]);
if(i==1) continue;
t1=(h1[p[k]+i-1]-h1[p[k]-1]*b1[i]%m1+m1)%m1;
t2=(h2[p[k]+i-1]-h2[p[k]-1]*b2[i]%m2+m2)%m2;
t=find(t1,t2);
if(t)
{
ans[t]^=ans[k];
continue;
}
add(t1,t2),ans[tot]=ans[k],p[tot]=p[k],v[i-1].push_back(tot);
}
v[i].clear();
}
printf("%d\n",mx);
}
int main()
{
int T;
scanf("%d",&T);
while(T--) work();
return 0;
}