manacher
维护目前右端点最靠右的回文串 \([l,r]\)，只记录中心 \(mid\) 和 \(r\) 即可
那么求 \(i\) 的最长回文半径时如果在 \(r\) 以左，那么直接可以从回文串的另一半继承过来
之后暴力枚举尝试扩展右端点
时间复杂度是 \(O(n)\) 是因为右端点的移动是单调的，而每次移动才会产生复杂度
注意这样同时可以证明一个串中本质不同的回文串的个数是 \(O(n)\) 的，因为只有暴力扩展的时候才会产生不同的回文串
由于有回文中心在中间的情况，那么在每个空隙中插入特殊字符进行计算即可
注意一开始的特殊字符不能少
对于回文长度是 \(p[t]-1\) 因为相当于除了回文中心两侧的特殊字符与原本字符一一对应补齐空位
void manacher(){
a[0]='#';
a[cnt=1]='?';
for(int i=1;i<=len;i++){
a[++cnt]=c[i];
a[++cnt]='?';
}
for(int t=1,mid=0,r=0;t<=cnt;t++){
if(t<=r)p[t]=min(p[mid*2-t],r-t+1);
while(a[t+p[t]]==a[t-p[t]])p[t]++;
if(t+p[t]>r)r=p[t]+t-1,mid=t;
ans=max(ans,p[t]-1);
}
}
首先可以一遍 \(kmp\) 处理出所有 \(s2\) 左端点出现的位置并赋值为 \(1\)，那么对于一个区间相当于是区间求和
对于每个回文中心，其实只需要知道最大回文半径即可，因为中间的回文串每次端点向内收缩 \(1\) 的长度，加的次数形成了一个等差数列，运用求和公式和前缀和处理即可
由于只需要求 \(max\)，那么只需要对本质不同的回文串进行计算即可
对于每个回文串的判断可以 \(O(1)\) 实现，在其 \(1/4\) 之处进行判断即可
而不同回文串诞生的时候是右端点移动的时候
回文自动机
回文自动机保存了所有本质不同的回文子串
和 \(AC\) 自动机一样，指针 \(nxt\) 表示回文子串中极大回文后缀
由于对称轴有奇偶之分，需要建立两棵树，分别保存长度为奇数和偶数的回文串
至于模板，反正也不长，理解的基础上还是建议背会吧……
P5496 【模板】回文自动机（PAM）
P3649 [APIO2014]回文串
首先是模板题，以一个位置结束的回文串个数等于 \(fail\) 树上的深度
一个回文串出现的次数是子树和
void pre(){
last=len[0]=0;
tot=nxt[0]=nxt[1]=1;
len[1]=-1;
return ;
}
int get_nxt(int p,int id){
while(a[id]!=a[id-len[p]-1])p=nxt[p];
return p;
}
void insert(int w,int id){
int p=get_nxt(last,id);
if(!son[p][w]){
int now=++tot;
len[now]=len[p]+2;
nxt[now]=son[get_nxt(nxt[p],id)][w];
dis[now]=dis[nxt[now]]+1;
son[p][w]=now;
}
last=son[p][w];
return ;
}
因为需要两个串的匹配，那么首先分别建出回文自动机
加入两棵自动机上都到了同一节点，那么这个回文串是共有的
那么同步进行 \(dfs\) 即可
也是一样的道理，只不过数数的过程用乘法原理来计算即可
根据定义，相应地应该引进一个新的指针：指小于其长度一半的最长回文后缀
然后根据题意模拟即可
注：以下部分在复习时被鸽掉，故不保证质量
P4762 [CERC2014]Virus synthesis
发现一个串可以由翻折得到需要满足那个回文子串小于其长度的一半，这和上面定义的指针恰好吻合
考虑进行 \(dp\)，设 \(f[i]\) 表示自动机上走到 \(i\) 节点的最小步数
那么有两种转移：要么是由一个回文子串添加一个字符，要么由一个小于一半的回文子串翻折而来
那么 \(f[i]=min(f[nxt[i]]+1,f[to[i]]+1+len[i]/2-f[to[i]]\)，因为添加字符肯定是先加再翻折更优
那么答案是 \(min\{n-len[i]+f[i]\}\)
接下来就要进入玄学部分了——最小回文划分
首先贴下链接，以后肯定再学：1，2，3，这里只略写一下目前的理解：
首先，这个问题考虑朴素的 \(dp\)，\(f[i]=f[j]+1([j+1,i]是一个回文串)\)
考虑一个点的回文子串，它们的转移是相似的，可以通过这一点进行优化
比如 \(aababab\)，\(f[aababab]\) 的转移是 \(f[aa],f[aaba],f[aababa]\)
那么考虑 \(f[aabab]\) 的转移有 \(f[aa],f[aaba]\)
发现了转移的高度相似性，而经过一系列的证明可以推导出树高是 \(log\) 的结论
然而至于什么样的串放进一类，以及构建出的具体形态还并没有搞清
重点是向回文划分的转化：
由于 \(s1=s_k\)，可以想到如果把后一半倒序插入前一段中就转化为回文串问题
具体地，\(s_1s_ks_2s_{k-1}\dots\)，可以自行手模验证
注意这样转化后要求是偶回文串划分，只有偶数节点可以进行 \(dp\) 转移
按照 \(a_1b_1a_2b_2\) 的顺序插入即可
和 \(AC\) 自动机一样，\(fail\) 树上可以搞很多东西
回文自动机上两点的 \(lca\) 的意义是两个回文串最长公共回文后缀
那么这道题只需要翻转一份到后面，每次查询转化为两个区间最长公共回文后缀问题，由于可能超过范围，倍增一下即可