【模板】回文字符机 PAM
【模板】回文自动机 PAM
回文自动机
定义
回文自动机（Palindrome Automaton）是处理回文问题的利器。类似后缀自动机，回文自动机有：
- 状态：每个回文子串是一个状态，没有两个状态代表相同的回文子串。
- 转移：从一个状态出发有转移边，字符 \(r\) 的转移边表示在两边加上 \(r\) 所对应的回文子串，或者没有。
- Fail 指针：Fail 指针指向这个回文子串的一个后缀，满足它也是回文子串。
引理
对于一个回文串 \(s\)，它有一段后缀 \(t\)，满足：
- 如果 \(t\) 是 border，那么 \(t\) 是回文串（正着读和反着读确实一样）
- 如果 \(t\) 是回文串，那么 \(t\) 是 border（因为正着读和反着读一样）
以下是非常形象的证明：
所以我们的 fail 指针实际上指的是最长 border。
构建
先说怎么构建再谈正确性：首先我们需要一个偶回文根 \(0\) 和奇回文根 \(1\)（都是空的），并使得 \(fail_0=1\)。记录 \(len_u\) 表示这个状态对应的回文子串的长度，\(len_1=-1\)。欲将插入字符 \(s_i\)，要从上次插入的地方 \(last\) 开始，我们要找到：谁的转移边应该到 \(u\)？\(u\) 的 fail 指针指向谁？
- 我们沿着 fail 树往上跳，跳到第一个满足：\(s[i-len[p]-1]=s[i]\) 的 \(p\)，那么这个 \(p\) 的转移边 \(ch_{p,r}\) 应该就是我们新的回文子串。
- 如果 \(ch_{p,r}\) 已存在，算法结束，返回 \(last=ch_{p,r}\)；否则新建点 \(ch_{p,r}:=u\)。
- \(len_u=len_p+2\)（由 \(len\) 定义）
- \(fail_u\) 的求值需要再跳一次 fail，找到另一个满足那个条件的，\(fail_u\) 就是它的 \(r\) 的转移边。
- \(last=u\)。结束。
观察到这个算法为什么没有更新其它的转移边，原因很简单，因为已经有了。可以理解一下，\(p\) 前面有一个 \(r\)，往上跳到一个 \(q\) 前面也有 \(r\) 的话，根据 \(p\) 的回文，\(q\) 的在左面的映射的后面有 \(r\)，同时前面有 \(r\)，那么说明 \(q\) 的 \(r\) 的转移边已经存在，这个回文串已经被创建。这同时证明了一个串的回文子串最多有 \(O(n)\) 个，上界在 aa...a 取得。
code
template<int N,int M> struct palindam{
int s[N+10],cnt,ch[N+10][M],fail[N+10],len[N+10],tot;
int trans[N+10];
palindam():cnt(0),tot(1){fail[0]=1,len[1]=-1;}
bool diff(int p){int i=cnt-len[p]-1; return i<0||s[i]!=s[cnt];}
int getfail(int p){while(diff(p)) p=fail[p]; return p;}
int expand(int p,int r){
s[++cnt]=r,p=getfail(p);
if(ch[p][r]) return ch[p][r];
int u=++tot; len[u]=len[p]+2;
fail[u]=ch[getfail(fail[p])][r];
return ch[p][r]=u;
}
};
应用
双回文子串
我们枚举每个回文子串，那么我们就要找到他的 fail 祖先中刚好等于它的长度一半的 border。当然可以树上倍增，但我们可以维护一个指针 \(trans_u\) 表示 \(u\) 的祖先中 \(\leq len_u/2\) 的一个 border，枚举的时候查验一下是不是等于即可。在新建点的时候维护 \(trans\)，首先如果 \(len_u\leq 2\) 那么取它的父亲即可，否则从 \(trans_p\) 开始向上跳，设跳到 \(q\)，则 \(len_q+2\leq len_u/2\) 时且合法时停下（1. 这相当于跳 \(fail_u\) 2. 常数次跳跃），然后取 \(trans_u=ch_{q,r}\) 即可。
if(len[u]<=2) trans[u]=fail[u];
else{
int q=trans[p];
while(diff(q)||(len[q]+2)<<1>len[u]) q=fail[q];
trans[u]=ch[q][r];
}
回文划分
见 https://oi-wiki.org/string/pam/
这里抛出一些结论：
- Weak periodicity lemma：若 \(p,q\) 都是字符串 \(s\) 的 period，\(p+q\leq |s|+1\)，则 \(\gcd(p,q)\) 也是 period。
- 所以，一个串的所有 border 构成 \(O(\log n)\) 个等差数列。
要做回文划分，就是 \(dp_i=1+\min_{j}f_j\) 其中 \([j-1,i]\) 回文，那么这个回文就是每个点插入的时候返回的点和他们的 fail，根据刚才的结论优化 DP 即可。