【学习笔记】PAM & Manacher

PAM & Manacher,两种用来处理回文串的玩意儿。

$1$ Manacher

挺短,背是挺好背的

Manacher用于求回文串长度。思想大概就是:

1、加入字符集之外的识别字符(比如#)分隔开原来相邻的字母,这样所有的回文串都变成了以某个字符为中心的(否则如果是偶数长度的回文串还要特判)。

2、考虑借由以前的信息求出新的回文串长度。记录到现在为止最靠右的回文串中最右侧的字符下标&其对称轴的下标,不妨记这个最靠右的串为$\rm S$。那么考虑以当前位置作为对称轴的答案,一定至少是$\min${隔着$\rm S$的对称轴与其对称的另一个位置ans,$|S|-i+1$} 。然后就不断扩展即可。

3、关于复杂度证明。我们记一次帅气的操作的意义是成功让$ans_i$的初始值继承了与之对称的点的答案和边界的取$\min$,记以当前点为轴的最长回文子串为$\rm T$,$T$的右端点为$q$。可以知道

  • (1)$\rm S$的右端点是单增的;
  • (2)如果当前旧的$maxlen<i$,即未成功进行一次帅气的操作,那么显然while1次,$maxlen$增大一次;
  • (3)如果当前的串经过了一次帅气的操作,那么当$q<maxlen$时,直接跳出while;当$q\geq maxlen$时,$q$增大$maxlen$必增大。所以得出结论,进行一次帅气的操作和$maxlen$的增大次数是严格同阶的。

So,最终复杂度就是$\Theta(n)$的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Manacher(char *s){
int id, fars, i ;
id = 0, fars = 0 ;
//id : 最靠右的回文串的中心位置
//fars : 迄今为止最靠右的回文串的最右侧
for (i = 1 ; i <= N ; ++ i)
ns[++ L] = (int)In[i], ns[++ L] = '#' ;
for (i = 1 ; i <= L ; ++ i){
if (fars <= i) base[i] = 1 ;
else base[i] = min(fars - i + 1, base[id * 2 - i]) ;
while (ns[i + base[i]] == ns[i - base[i]]) base[i] ++ ;
if (i + base[i] > fars) id = i, fars = i + base[i] - 1 ;
}
}
int main(){
scanf("%s", In + 1),
L = -1, N = strlen(In + 1) ;
ns[++ L] = '$', ns[++ L] = '#' ; Manacher(In) ;
for (int i = 1 ; i <= 2 * N + 2 ; ++ i) ans = max(ans, base[i] - 1) ;
cout << ans << endl ; return 0 ;
}

$2$ PAM

学了PAM,不知道为啥感觉比SAM简单?

其实就是一种自动机,以回文串为状态,左右各添加一个字符为转移的自动机。要点如下:

0、一个串的回文子串至多有$O(n)$个。

1、首先每个节点需要保存这个节点中回文串的长度。

2、显然始状态需要有两个,即奇数长度的$s$和偶数长度的$s$,称作“奇根”“偶根”。那么为了方便呢,奇根的长度设置为$-1$,偶根长度设置为$0$。

3、考虑要从$last$指针扩展当前状态,假设当前需要insert的字母是$c$,是这个串里面的第$p$个字符,那我们需要找到一个后缀$s[j…p-1]\quad s.t.\quad s[j…p-1]$本身回文且$s[j-1]=c$,那么就可以向下扩展。

4、考虑怎么找这个后缀,显然对于一个串$S$,他的所有回文后缀都是其最长回文后缀的回文后缀。所以考虑$fail$指针,应当从当前状态连向它的最长回文后缀

5、插入新节点时,考虑跳完$fail$后如果没有相应的转移边,就要新建一个状态然后连$fail$.

然后是代码和一点注意:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct PAM{
int trie[MAXN][Sigma] ;
int rt0, rt1, last, sz ;
int len[MAXN], fail[MAXN] ;
}P ;
void _init(PAM &p){
p.sz = -1,
p.rt0 = ++ p.sz, p.rt1 = ++ p.sz ;
p.fail[p.rt0] = p.fail[p.rt1] = p.rt1 ;
p.last = p.rt0, p.len[p.rt0] = 0, p.len[p.rt1] = -1 ;
}
void _insert(PAM &p, int x, int pos, char *s){
int u = p.last ;
while (s[pos - p.len[u] - 1] != s[pos]) u = p.fail[u] ;
if (!p.trie[u][x]){
int fa = p.fail[u] ;
int newn = ++ p.sz ;
p.len[newn] = p.len[u] + 2 ;
while (s[pos - p.len[fa] - 1] != s[pos]) fa = p.fail[fa] ;
p.fail[newn] = p.trie[fa][x], p.trie[u][x] = newn,
}
p.last = p.trie[u][x] ;
}

6、$\rm \color{red}{WARNING}$,以下两句顺序不要写反:

1
p.fail[newn] = p.trie[fa][x], p.trie[u][x] = newn,

原因是当$fa=u$时就出现环了。

$3$ 闲扯

学完才知道,$\rm PAM$又简单又好背功能又多……Manacher被打爆了啊喂qwq。