【BZOJ4166】月宫的符卡序列 Manacher+hash

【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;
}