回文自动机
chihik
·
·
个人记录
一.概念
1.回文自动机
回文自动机，又叫回文树，是一种能在\Theta(n)时间玄学解决回文串问题的一种结构，代码难度也十分和蔼可亲。
回文树上的每个节点都代表一个不同的回文子串，相同的回文子串在同一节点。
值得注意的是，回文树上有两个根，0根以及-1根，分别表示空串和-1串，其本质是考虑奇串和偶串。
回文树上有两种边，一种是转移边，另一种是后缀边。
2.转移边
若回文串 S 有一条 ch 的转移边到 S' ，说明存在一个回文串 S 两端各增加1个字符 ch ，将形成回文串 S' 。
特殊的，对于 -1 根的转移边，表示单个字符表示的回文串，如 a。
3.后缀边
若回文串 S 有一条后缀边连接到 S' ，说明 S' 是 S 的最大回文串后缀（不含S 自身）。
对于 0 根和 -1 根，其后缀边都连向 -1 根，为的是统一奇串和偶串。
因为每个节点只会向上有一条后缀边，所以所有后缀边会形成一棵树。
4.例子
黑色的边为转移边，红色的边为后缀边。
如图，5号节点代表的回文串为 bab , 9号节点代表的回文串为 caac
二.构造
和后缀自动机一样，回文自动机使用增量法构造。在构造之前，定义一些变量：
$Link[u]$ , 点 $u$ 的后缀边指向的点。
$Len[u]$ , 点 $u$ 所表示的回文串的长度。特殊的，为了得到奇串$-1$ 根的 $Len$ 为 $-1$。
$str[i]$ 表示需要构造的串的第 $i$ 位。
$Last$ , $str[i-1]$ 为右端点的最长回文子串的标号（必定存在，因为可以单独一个字符作为回文串）。
***
若 $str[i-len[Last]-1]≠str[i]$ ，即 $i-1$ 的最长回文串无法通过前后拓展一个字符 $S[i]$ 形成更长的回文串。
那么我们将 $Last$ 设为 $Link[Last]$ ，寻找它的最长回文后缀，最终一定能找到。最坏情况下来到 $-1$ 根 ， 此时一定满足条件。将现在到达的点记为 $u$ 。
找到后，说明 $u$ 可以前后加上 $str[i]$ 形成一个更长的回文串，那么$str[i]$为右端点的最长回文串就找到了。
1. 若此时 $Trans[u][str[i]]$ 不等于 $0$ ，也就是已经有一个这样的回文串了，那么将 $Last$ 设置为 $Trans[u][str[i]]$ , 结束。
2. 若不存在这样的回文串，需要新建一个节点 $Newnode$ 表示这个回文串。将 $Trans[u][str[i]]$ 设为 $Newnode$ ，并将 $len[Newnode]$ 设为 $len[u]+2$ 。顺着 $u$ 的 $Link$ 链走，直到再次出现 $str[i-len[u]-1]=str[i]$ 的位置， 此时将 $link[Newnode]$ 连向 $Trans[u][str[i]]$ 即可。
图解过程可以看看[这篇博客](https://www.cnblogs.com/nbwzyzngyl/p/8260921.html)。
## 三.复杂度
### 1.空间复杂度
空间复杂度是 $\Theta(nk)$ ，$n$是字符串长度 ， $k$ 是字符集大小。
不过可以通过$\text{Map}$优化空间。
### 2.时间复杂度
并不会证明，大概是建立后缀边的时候，一旦走过了一个点，之后再在后缀链上走时将会跳过该点。也就是复杂度均摊 $\Theta(n)$。
## 五.例题
先附一份模板：
```cpp
struct Palindromes_Automaton {
int Size , Last , Root0 , Root1 , Trans[ MAXN + 5 ][ MAXK + 5 ] , Link[ MAXN + 5 ];
int Len[ MAXN + 5 ];
Palindromes_Automaton( ) {
Root0 = Size ++ , Root1 = Size ++; Last = Root1;
Len[ Root0 ] = 0 , Link[ Root0 ] = Root1;
Len[ Root1 ] = -1 , Link[ Root1 ] = Root1;
}
void Extend( int ch , int dex ) {
int u = Last;
for( ; str[ dex ] != str[ dex - Len[ u ] - 1 ] ; u = Link[ u ] );
if( !Trans[ u ][ ch ] ) {
int Newnode = ++ Size , v = Link[ u ];
Len[ Newnode ] = Len[ u ] + 2;
for( ; str[ dex ] != str[ dex - Len[ v ] - 1 ] ; v = Link[ v ] );
Link[ Newnode ] = Trans[ v ][ ch ]; Trans[ u ][ ch ] = Newnode;
}
Last = Trans[ u ][ ch ];
}
void Build( char *str ) {
int len = strlen( str );
for( int i = 0 ; i < len ; i ++ )
Extend( str[ i ] - 'a' + 1 , i );
}
}PAM;
```
### 1.[P5496 【模板】回文自动机（PAM）](https://www.luogu.com.cn/problem/P5496)
#### [题解](https://www.luogu.com.cn/blog/chihik/solution-p5496)
### 2.[SP7586 NUMOFPAL - Number of Palindromes](https://www.luogu.com.cn/problem/SP7586)
#### [题解](https://www.luogu.com.cn/blog/chihik/solution-sp7586)
### 3.[P3649 [APIO2014]回文串](https://www.luogu.com.cn/problem/P3649)
#### [题解](https://www.luogu.com.cn/blog/chihik/solution-p3649)
### 4.[P4555 [国家集训队]最长双回文串](https://www.luogu.com.cn/problem/P4555)
#### [题解](https://www.luogu.com.cn/blog/chihik/solution-p4555)
### 5.[CF17E Palisection](https://www.luogu.com.cn/problem/CF17E)
#### [题解](https://www.luogu.com.cn/blog/chihik/solution-cf17e)
### CF835D Palindromic characteristics
### CF159D Palindrome pairs
### CF932G Palindrome Partition