题目大意

给定一个包含26个小写字母的字符串，字符从0开始标号。一个子串a的价值定义为：a在S中的所有出现位置中点的异或值。(规定：若a出现在s[l……r],那么a的中点为$\frac{l+r}{2}(向下取整)$).求：对于所有 回文子串 a，最大的价值是多少？

输入格式

第一行，一个整数num,($1\leq num\leq 5$)，表示数据组数；
每组数据占一行，有一个仅含小写字母的字符串S.

输出格式

对于每组数据，输出一行，表示最大价值.

样例

样例输入

1
aabacabaaa

样例输出

15

样例说明

对于回文子串aa,所有出现位置的中点为:0,7,8;
0^7^8=15

题解

回文自动机记的是右端点，似乎不太好用，关键是我不会写回文树。
所以还是考虑一下manacher+hash.
先用manacher跑一遍字符串，可以看出，只有在暴力扩展右边界时会产生新的本质不同的回文串.
这些本质不同的回文串的数目是O(n)的。
我们需要把中间部分相同的串连接起来形成一棵树.
比如:abbba是bbb的子节点，bbb是b的子节点.子串用hash值映射到节点.
本来用的是map，发现超时很严重，于是看了下网上各位大佬的代码，发现大佬们用的是hash_table.
居然用黑科技！我等蒟蒻还是用链表hash算了。

代码(很丑)

#include<cstdio> 
#include<cstring> 
#include<algorithm> 
#include<map> 
using namespace std; 
#define MAXN 1005000 
#define LL long long 
#define ULL unsigned long long 
const ULL s1=131,s2=129; 
const ULL m1=19980403,m2=998244353; 
char s[MAXN],t[MAXN*2]; 
ULL h1[MAXN],h2[MAXN],pow1[MAXN],pow2[MAXN];
int Next[MAXN<<2],End[MAXN<<2],Last[m1+10],Len[MAXN<<2],e=0;
void add(ULL x,int p)
{ULL a,b;a=x>>32;b=x-(a<<32);End[++e]=b;Len[e]=p;Next[e]=Last[a];Last[a]=e;return ;
}
int find(ULL x)
{ULL a,b;a=x>>32;b=x-(a<<32);for(int t=Last[a];t;t=Next[t]){if(End[t]==b){return Len[t];}}return -1;
}
int L,len; 
map<ULL,int>T; 
void init() 
{ pow1[0]=pow2[0]=1; h1[0]=h2[0]=0; for(int i=1;i<=L;i++) { pow1[i]=pow1[i-1]*s1%m1; pow2[i]=pow2[i-1]*s2%m2; h1[i]=(h1[i-1]*s1+s[i])%m1; h2[i]=(h2[i-1]*s2+s[i])%m2; } return ; 
} 
ULL cal(int l,int r) 
{ ULL t1,t2; t1=(h1[r]+m1-h1[l-1]*pow1[r-l+1]%m1)%m1; t2=(h2[r]+m2-h2[l-1]*pow2[r-l+1]%m2)%m2; return (t1<<32)|t2; 
} 
int fa[MAXN],dp[MAXN],p[MAXN*2],tot=0,ans=0; 
void work() 
{ memset(p,0,sizeof(p));memset(s,0,sizeof(s));memset(Last,0,sizeof(Last));e=0;//T.clear(); tot=0; scanf("%s",s+1); L=strlen(s+1); init(); t[0]='$'; len=0; for(int i=1;i<=L;i++) { t[++len]='#'; t[++len]=s[i]; } t[++len]='#'; t[++len]='@'; int mx=0,id=0,lst; ULL tt;for(int i=1;i<len;i++) { p[i]=mx>i?(min(mx-i,p[(id<<1)-i])):1; //lst=(p[i]==1)?0:T[cal(((i-p[i])>>1)+1,(i+p[i]-1)>>1)];lst=(p[i]==1)?0:find(cal(((i-p[i])>>1)+1,(i+p[i]-1)>>1)); for(;t[i-p[i]]==t[i+p[i]];) { ++p[i]; tt=cal(((i-p[i])>>1)+1,(i+p[i]-1)>>1);if(find(tt)<0) { //T[tt]=++tot;++tot;add(tt,tot); dp[tot]=0;fa[tot]=lst; lst=tot; } else { //lst=T[tt]; lst=find(tt);} } if(lst) { dp[lst]^=(i>>1)-1; } if(i+p[i]>mx) { mx=i+p[i]; id=i; } } ans=0; for(int i=tot;i>=1;i--) { ans=max(ans,dp[i]); dp[fa[i]]^=dp[i]; } printf("%d\n",ans); return ; 
} 
int main() 
{ int Tt; scanf("%d",&Tt); while(Tt) { work(); --Tt; } return 0; 
}

上面这段丑代码，显然是用了map发现T了，然后改成链表的。链表部分的变量名沿用了链式存图的变量名.