通过在字符串之间的每个空位内插入字符，是的奇数和偶数成为一样得情况，从而能够统一处理。
用len[]记录每个点能够扩展出的最长半径，mx记录扩展到的最远右端点，id记录mx为右端点时的mid，即对称轴，设i关于mid的对称轴为j。
关于i和mx的位置进行分类讨论：
若i在mx右边，则直接进行暴力。
否则，首先对len[i]取len[j]和i到mx的距离的较小值，因为对于i+ken[j]>mx的情况，无法确定在mx之外i是否还能够继续进行匹配，所以在mx这里截断，之后进行暴力，并更新mx和id.
注意这里的len[i]是包括i自己的。
首先是插入分隔符。
s[k++]='~';/*修改字符串*/
for(int i=0;i<n;i++)s[k++]='|',s[k++]=a[i];/*插入分隔符和原字符*/
s[k++]='|';
s[k]=0;/*末尾终止符*/
之后是进行Manacher算法。
inline void Manacher(char s[],int n){
int mx=0,id=0;
for(int i=1;i<n;i++){
if(i<mx)len[i]=min(mx-i/*防止越界*/,len[(id<<1)-i]/*对称点*/);/*用i关于mid的对称点来更新i*/
else len[i]=1;/*初始化之后进行暴力计算*/
while(s[i+len[i]]==s[i-len[i]])len[i]++;/*暴力扩展*/
if(len[i]+i>mx){/*更新mx和id*/
mx=len[i]+i;
id=i;
}
}
}
max{len[i]}-1即为整个串的回文串最大长度。
若中心为分隔符，那么从分隔符到回文边界的分隔符，共有字符len个，恰好比原字符个数多1个，那么整个区间的回文长度就是(len-1)/2*2=len-1.
若中心为原字符，那么到回文边界的分隔符，len肯定为偶数，这段区间内的原字符的个数为len/2个，整个区间的回文长度就是len/2*2再减去算重的回文中心，即len-1.
若求回文串个数，sum(i=1->n)(len[i]/2)即为答案。
一个和谐小团体为长度为奇数的回文串，将其按个数降序排序后，求前k个的个数的乘积。在计算每个点能够扩展出的最长半径时为每个半径开桶记录，之后倒叙扫描每个桶并用快速幂计算。
inline void Manacher(char s[],int n){
int mx=0,id=0;
for(int i=1;i<=n;i++){
if(i<mx)len[i]=min(mx-i,len[(id<<1)-i]);
else len[i]=1;
while(s[i-len[i]]==s[i+len[i]])len[i]++;
if(i+len[i]>mx){
mx=i+len[i];
id=i;
}
if(len[i]-1&1)cnt[len[i]-1]++;
}
}
for(int i=n;i;i--){
if(i&1){
m+=cnt[i];
if(k>=m){
(ans*=po(i,m,mod))%=mod;
k-=m;
}
else{
(ans*=po(i,k,mod))%=mod;
k-=m;
break;
}
}
}
求一个字符串的最长双回文子串T，即T可以分为两部分非空的不相交回文串。考虑记录记录每个点作为一个回文串的左右端点时回文串的长度，可以在求len时得到，但是这样下的长度仅是饱和回文串，不饱和回文串需要再次通过递推得到。递推时枚举分隔符，对于l[i]，由l[i-2]-2得到，因为l[i-2]有可能包含着l[i]。对于r[i]，由r[i+2]-2得到，因为r[i+2]有可能包含着r[i]，更新答案时需要左右都能够构成回文才进行更i性能不能只有一方由回文。
inline void Manacher(char s[],int n){
int mx=0,id=0;
for(int i=1;i<=n;i++){
if(i<mx)len[i]=min(mx-i,len[(id<<1)-i]);
else len[i]=1;
while(s[i-len[i]]==s[i+len[i]])len[i]++;
if(i+len[i]>mx){
mx=i+len[i];
id=i;
}
l[i-len[i]+1]=max(l[i-len[i]+1],len[i]-1);
r[i+len[i]-1]=max(r[i+len[i]-1],len[i]-1);
}
}
for(int i=3;i<=k;i+=2)l[i]=max(l[i],l[i-2]-2);
for(int i=k-2;i>=1;i-=2)r[i]=max(r[i],r[i+2]-2);
int re=0;
for(int i=1;i<=k;i++)if(l[i]&&r[i])re=max(re,l[i]+r[i]);
定义字符串反转操作为将前|S|-1个字符倒叙插入到S后面，给出S，问有多少种长度小于|S|的字符串R使得R翻转若干次后S是R的前缀。由翻转可以联想到回文，算出每个点的最大回文半径，若右端点覆盖了S右端点，那么一次翻转即可，若左端点覆盖了S左端点，再次判断右端点是否合法即可，倒叙遍历，注意k是长度，要减去字符串末尾终止符。
for(int i=k;i;i--)if((i+len[i]-1==k)||(vis[i+len[i]-2]==true&&i==len[i]))vis[i]=true;
for(int i=1;i<=k;i++)if(s[i]!='|'&&vis[i]==true)cout<<(i>>1)<<' ';
求一个字符串在异或意义下的回文串个数。将直接判断相等改为判断0->1,1->0分隔符对应自己相等即可。
inline char to(char c){
switch(c){
case '0':return '1';
case '1':return '0';
case '~':return '~';
case '|':return '|';
default:return '!';
}
}
inline int Manacher(char s[],int n){
int id=0,mx=0,re=0;
for(int i=1;i<=n;i+=2){
if(i<mx)len[i]=min(mx-i,len[(id<<1)-i]);
else len[i]=1;
while(to(s[i+len[i]])==s[i-len[i]])len[i]++;
if(i+len[i]>mx){
mx=i+len[i];
id=i;
}
re+=len[i]>>1;
}
return re;
}