回文自动机

回文自动机Palindromic Automaton(又称回文树Palindromic Tree,简称pam)能干什么?

对于字符串S[1..n],比如它可以求出S的所有本质不同的回文子串,并求出每一个本质不同的子串在S中出现的次数,当然还能干别的很多事情。

现在来看回文自动机是如何构建的。

定义变量:

cnt表示pam中的节点数,pam的每一个节点分别表示一个本质不同的回文串子串

trans[u][c]表示在节点u所对应的回文子串两边加入字符c时变成的回文串对应的节点(可能不存在)

len[u]表示节点u表示的回文子串的长度

fail[u]表示结尾与u表示的回文子串相同,长度小于len[u]的最长的回文子串所对应的节点(类似AC自动机和KMP的失配指针)

n表示当前字符串的长度(和sam类似,pam也是增量构造的)

s[1..n]表示当前的字符串

last表示结尾是n,长度最长的回文子串对应的节点

num[u]表示u节点表示的回文子串在s[1..n]中出现的次数(这个在增量构造中是不能直接计算的,如果一定要算需要数据结构,因为num[fail[u]]要加在num[u]上,但可以在最后一次性算)

初始化:

一开始pam上有两个节点,0号点和1号点,分别是长度为偶数的回文串的根和长度为奇数的回文串的根。0号点的长度为0,1号点的长度为-1,因为最短的偶数长度的回文串长度是2,奇数的是1,所以减2后是0和-1,感性理解一下。

在最后加入一个字符:

假设当前加入的字符串为s[1..n-1],现在加入字符s[n]。首先找到一个结点u,其对应的字符串要满足结尾为n-1,s[n]==s[n-len[u]-1],长度最大。这个节点只要沿着fail指针向上枚举就可以了,类似KMP。然后如果trans[u][s[n]]存在,则last就等于那个节点,否则如果trans[u][s[n]]不存在,则说明找到了一个与已经找到的回文子串本质不同的回文子串,所以要新建节点v,trans[u][c]就要指向v,len[v]就等于len[u]+2,fail[v]根据定义,应该为trans[w][c],w对应的字符串要满足结尾为n-1,s[n]==s[n-len[w]-1],len[w]<len[u]且len[w]尽可能大。这个求的过程与求u的过程类似。

复杂度

时间复杂度是O(n lg$\sum$),空间复杂度是O(n $\sum$)

模板

BZOJ3676

3 条评论
  1. I truly wanted to jot down a note to express gratitude to you for the fabulous tips and hints you are posting on this site. My time-consuming internet search has now been compensated with really good details to exchange with my good friends. I ‘d mention that most of us readers are very blessed to dwell in a useful site with very many wonderful people with insightful basics. I feel quite blessed to have used your website page and look forward to plenty of more cool moments reading here. Thanks a lot once more for everything.

发表一条评论