\(Manacher\) (马拉车)

作用：可以在线性复杂度下求出每个点的最长回文半径

算法流程：

step1. \(manacher\) 只能解决有对称中心的回文串，因此需要将所有回文串转化为有对称中心的，具体操作就是在每两个字符之间插入一个无关字符，并在首尾都插入无关字符
step2. 从左到右依次处理，记录一下当前最远有边界和其对应的对称中心。现在新插入了一个i，需要分类讨论：
- 若 \(i<mr\) 意味着在对称中心的左侧，有一个和他一样的点，而那个点我们已经算过了，无需再算，因此 \(p_i=p_{mid \times 2-i}\)，但是仍有一点小问题，就是左侧的对应点是否出了大范围的界限，若溢出了，则 \(p_i=mr-i\)。但是我们不知道1.2情况下他是否还能继续拓展，因此 \(p_{ireal} \ge p_i\)
- 若\(i \ge mr\)，意味着当前没有对称点可以快速求出，我们暂且设他为1
step3. step2留下了遗留问题就是他是否可以继续拓展，因此我们暴力拓展就行了，最后不要忘记更新 \(mr\) 和 \(mid\)

最后答案不要忘记转化，找规律可知道是： \(max_{mid==i}=p_i-1\)

代码：

void init()
{
	b[k++] = '#',b[k++] = '#';
    for(int i=0;i<n;i++)
    {
        b[k++]=a[i],b[k++]='#';
    }
    b[k++]='^';
    n=k;
}
void manacher()
{
    int mr=0,mid;
    for(int i=1;i<n;i++)
    {
        if(i<mr) p[i]=min(p[mid*2-i],mr-i); //分别对应，对称点未出界，对称点出界
        else p[i]=1; //i在外面
        
        while(b[i-p[i]]==b[i+p[i]]) p[i]++;
        if(i+p[i]>mr)
        {
            mr=i+p[i];
            mid=i;
        }
    }
}

时间复杂度证明：\(mr\)单调不减因此最多只会 \(+n\) 次，复杂度线性。

回文自动机（PAM）

和 \(trie\) 树类似，采用增量树，并且增加了回溯机制，方便日后处理

预处理需要处理虚跟问题，为方便处理，通常采取这种方式

//init:
	len[1]=-1;
	fail[0]=1;//防止死循环	
	tot=1;

简单来说，插入过程分为两步走

一、找到他的节点位置，由于采取增量树，因此我们需要知道他是从哪里增过来了，回文串掐头去尾亦是回文串，利用此性质可以找到它的父节点。

	int p=last;//以i-1结尾的最长回文串的编号即为last
	while(s[i-1-len[p]]!=s[i]) p=fail[p];

循环结束的时候，\(p\) 就是他的父亲了。

接下来分类讨论：

若p有 \(tr[p][c]\) 这个儿子，那么很好，直接走下去就好了，不需要维护

  if(tr[p][c])
  {
      //已经存在，不需要更新len，tr和fail 
      last=tr[p][c];
      ans=cnt[last];
      return ans;
  }

若没有他这个儿子，说明找到了一个新的本质不同的回文子串，因此需要加入这个节点。也就是说，要维护好他的减量对应父亲和失配指针，以及他的回文长度

	int k=fail[p],id=++tot; 
  	//维护失配指针
	while(s[i-len[k]-1]!=s[i]) k=fail[k];
	fail[id]=tr[k][c];//跟回文对称性可以得知一定有这个节点
	cnt[id]=cnt[fail[id]]+1;
	
	//最后再更新他的位置和长度 
	tr[p][c]=id;
	len[id]=len[p]+2;
	
	//存储last和ans 
	last=id;
	ans=cnt[last];
	return ans;

模板：
回文自动机

完整版代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
char s[N];
int fail[N],tr[N][30];
int len[N],cnt[N];
int n;
int last,ans,tot;

void init()
{
    fail[0]=1,fail[1]=0;
    len[1]=-1;
    tot=1;
}

int insert(int i,char c)
{
    int p=last;
    c-='a';
    
    while(s[i-1-len[p]]!=s[i]) p=fail[p];
    
    if(tr[p][c])
    {
        last=tr[p][c];
        ans=cnt[last];
        return ans;
    }
    
    int id=++tot,k=fail[p];
    while(s[i-1-len[k]]!=s[i]) k=fail[k];
    //更新fail
    fail[id]=tr[k][c];
    cnt[id]=cnt[fail[id]]+1;
    
    //更新位置
    tr[p][c]=id;
    len[id]=len[p]+2;
    
    //更新答案
    last=id;
    ans=cnt[last];
    
    return ans;
}

int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    
    init();
    
    for(int i=1;i<=n;i++)
    {
        if(i>1) s[i]=(s[i]-'a'+ans)%26+'a';
        
        printf("%d ",insert(i,s[i]));
    }
    
    return 0;
}

复杂度证明：？不会。我只知道是 \(O(n)\)

注意：需要重置回文树的时候，只需要再 \(init()\) 中增加重置 \(tr\) 数组即可

例题选做

1 .P5446 [THUPC2018] 绿绿和串串

关于这道题有非常有意思的故事，去年模拟赛有这个题然而我不会马拉车，不会哈希，dfs暴力拿了60 由于交错代码挂了50。。。

然后学了马拉车之后前一天半夜才做了这道题，第二天就是当前这场模拟赛的vp，太幸运了。。

言归正传：奇数回文，马拉车无疑了，但是关键是如何求答案呢。

通过观察可以发现，第一次翻折必须是要么左到头，要么是右到头。~~因此可以哈希~~。因此需要特判，并且如果没有一次对折完，需要看一下下一次的折叠点是否可行。

P1659 [国家集训队] 拉拉队排练

同样，仅统计奇数回文，考虑马拉车。

记录一下所有最长的回文串长度出现的次数，由于是最长的，因此长度为 \(3\) 的回文串一定在长度为 \(5\) 的回文串中出现了。因此需要进行一波前缀和。即从大到小枚举奇数长度，并实时维护前缀和。

P4555 [国家集训队] 最长双回文串

\(PAM\) 板子，如果做的多了就会有感觉，求中心点/奇数回文马拉车更好使，如果求的是结尾位回文还是回文树好用。

正着反着都跑一遍 \(PAM\)，记录每个位置的最左回文串长度和最右回文串长度。

最后枚举一下断点即可。

Prefix-Suffix Palindrome

先贪心，把两侧已经是对称的取了，然后在算最长前缀回文和最长后缀回文，马拉车和回文树都可。

最后的输出有点恶心，注意，如果字符串本身就是奇数长度回文即有中心点的回文，双指针到最后会分居中间位置的两侧，注意不要重复输出。

典型套路：

1.\(trans\) 指针

在回文自动机中，我们的失配指针是指向上一个以同一个字母结尾的回文串。

\(trans\) 指针则指向了 \(\le \frac{1}{2} \times len_i\) 的节点编号。

他的更新并不复杂，也是向上跳跃即可，不过要注意当 \(len \le 2\) 的时候，直接将他的 \(trans\) 指向 \(fail\) 否则可能导致死循环

   if(len[id]<=2) trans[id]=fail[id];
   else
   {
   	int j=trans[p];
   	while(s[i-len[j]-1]!=s[i]||(len[j]+2)*2>len[id]) j=fail[j];//问题在这里，有可能第二个条件永远满足。所以必须特判
   	trans[id]=tr[j][c]; 
   }

他具体用在什么地方呢，有的时候有些回文翻倍问题可以用 \(trans\) 指针很好的解决。

练习：

a. P4287 [SHOI2011] 双倍回文

如果一个回文串，首先满足他的长度是4
的倍数。

然后如果他的 \(trans\) 指针指向的节点对应的长度正好是他的一半，则找到了一个双倍回文串。更新答案即可。

\(trans\) 指针的基础应用

双倍经验

b.P4762 [CERC2014] Virus synthesis

不得不吐槽一下，回文自动机2014年才发明，这就考，离谱。

增加了dp。想象一下，他最后一次使用完对称反串的操作，一定对应的是一个构造出的串的回文串，剩下的不能用2操作了因为不可以再次倍长了。

因此剩下的部分只能用操作一补上。

现在我们就是要对每一个回文串，他所需要的代价进行求解，设第 \(i\) 个回文串所需要的代价是 \(f_i\)

\(ans=n-len_i+f_i\)

对于 \(f_i\) ,肯定有 \(f_i \le len_i\)

然后另外两种转移就比较难想了。

如果从回文树的结构来看还是有逻辑可循的

首先它对应的减量父节点可以转移到他，代价仅为1，在父节点形态仍处于他的一半的时候增加一个增量字母即可。

回溯机制有两个

\(fail\) 方向：不知道是否是偶数，暂且放过。
\(trans\) 方向：\(f_i= \frac{len_i}{2}-len_{trans_i}+f_{trans_i}+1\)，含义为利用1操作不全 \(trans\) 为其完整一半，在倍长即可。

仔细想来如果他有偶数的 \(fail\) ，那么一定是-2的，那么至少需要两步才能补全，而对称过来只需要1步，也可以发现偶数长度失配指针的 \(f\) 也是从 \(trans\) 来的（欸呀其实没有想明白。。。）

用宽搜解决这个问题即可，必须用宽搜，因为可能会用到上面层的节点，必须一层一层处理。

2.最小回文划分模型

最小回文划分，顾名思义，将一个串进行划分，使得每一段都是回文串，最小化划分的段树。

另一种形式为求划分方案数，基本上相同，此处以最小化为例。

part1: 暴力

最优化问题可以考虑动态规划，又是一个分段问题，容易想到线性dp。

设 \(f[i]\) 表示对前 \(i\) 个字符进行划分，需要的最少步骤。

考虑最后一步我们一定是分出去了一个以 \(i\) 结尾的回文串，建立回文自动机，就有方程：

\[f[i]= \min_{x \in PAM}f[j-len[x]] \]

不过会发现，每个点结尾的回文串个数是 \(O(n)\) 级别的，这样下来复杂度就是 \(O(n^2)\) 的。

part2: 前置引入

1.引理：

建立 \(fail\) 树，每一条到根部的链，都可以划分为 \(\le logn\) 段等差数列。

并且，从下往上看，一段等差数列的结尾也是另一段等差数列的开始

为什么是等差数列呢，需要自己画个图明白。简单来说，可以发现最长回文后缀是个border，之后就好说了。

2.新定义：

引入两个数组：

\(diff[x]\)

表示节点 \(x\) 与 \(fail[x]\) 的长度差，形式化的说就是

\[diff[x]=len[x]-len[fail[x]] \]
\(slink[x]\)

表示 \(x\) 所在等差数列的顶部也是下一段等差数列的底部。形式化的说就是：

\[slink[x]=slink[fail[x],diff[x]=diff[fail[x]] \]
\[slink[x]=fail[x],diff[x]!=diff[fail[x]] \]
如果和父亲的差异一样，说明在一段上，如果不是，说明父亲正好是尾部和头部的交界点。

代码实现：

int insert(int i)
{
	int c=s[i]-'a',u=last;
	while(s[i]!=s[i-len[u]-1]) u=fail[u];
	if(tr[u][c]) return tr[u][c];
    
	int x=++idx,p=fail[u];
	while(s[i]!=s[i-len[p]-1]) p=fail[p];
	fail[x]=tr[p][c],tr[u][c]=x,len[x]=len[u]+2;
	
   	diff[x]=len[x]-len[fail[x]];
	if(diff[x]!=diff[fail[x]]) slink[x]=fail[x];
	else slink[x]=slink[fail[x]];
    
	return x;
}

3.辅助dp的g数组定义及维护

接着我们考虑dp，为了利用这个log的性质，我们有了大体方向：批量处理和维护一段等差数列。

因此我们令 \(g[x]\) 表示对于那些处于交界处的点 \(x\)，他所包含的向上一段等差数列中，所有位于左端点的 \(f[j]\) 的 \(min\)

g[x]

三个橙色的点对应的 \(f\) 就是 \(g[x]\) 所应该维护的。

有了 \(g\) 数组，我们只需要不断跳 \(slink\)，即可在 \(log\) 的复杂度内完成对于一个点 \(f\) 的更新。

考虑维护 \(g\) 依然采取增量的构造，观察下图：

蓝色的点构成的集合，是 \(g[fail[x]]\)；

我们需要的，是橙色的点构成的集合：\(g[x]\)

可以发现，只有最顶端的那个橙色点，是需要新加入的：\(f[i-diff[x]-len[slink[x]]]\)

不过，也不一定是所有情况都要继承 \(fail[x]\) 的 \(g\)，当两个点不在同一个等差数列，也就是说 \(x\) 是全新的一个等差数列，就只需要新加入即可。

具体的代码实现：

for(int i=1;i<=n;i++)
	{
		last=insert(i);
		for(int u=last;u>1;u=slink[u])
		{
			g[u]=f[i-diff[u]-len[slink[u]]];
			if(diff[u]==diff[fail[u]]) (g[u]+=g[fail[u]])%=mod;
			(f[i]+=g[u])%=mod;
		}
	}

5.回文划分模型的构造方法：

看题说话：

1.CF906E Reverses

题意：给你两个串，问可以任意选择某一区间反转，限制区间两两不相交，最终使得两串一样，问最少反转次数。

反转相等的翻译：

初级：两串首位拼接后构成回文串
高级：两串交叉拼接后构成回文串

为什么是这样划分更高级呢，因为它可以进行反推，也就是你任意划分出的回文串，都可以对应原来的一步操作。

该题具体做法：对两串交叉拼接，做最小偶回文划分，注意分割出长度为2的回文串免费。

2.CF932G Palindrome Partition

题意：给定一个串，把串分为偶数段，使得这偶数段首尾依次对应相等。

首位相等的翻译：正着念和倒着着念反转相等，对应了上面。

构造首尾交叉拼接串，进行偶回文划分即可。

3.等差数列的平移规律：

可以发现，每次等差数列的平移，都是将一批线段，整体向右移动了一个公差，可以发现，左端点改变的，只有一头一尾。

具体题目：「2017 山东一轮集训 Day4」基因

标签：int,tr,len,fail,字符串,id,回文
From： https://www.cnblogs.com/Richardwhr/p/18310264

字符串回文