Manacher算法&回文自动机

正好学了这两个东西,都是有关回文串的算法,所以干脆放到一起讲一下。

Manacher算法比较simple,跑的也和香港记者一样快,但同时也很naive。作用是\(O(n)\)求出以每个点为中心的最长回文字串。

算法的关键思想是:假设令\(len_i\)表示从以\(i\)为中心最多能向两边延伸多长的距离都是回文串,那么如果存在\(i<j\)满足\(i+len_i>j\),则\(len_j\ge min(i+len_i-j,len_{2i-j})\)。手画一下易知这个结论是对的。

于是用上这个,再暴力向两边扩展,保存右端点最右的最长回文子串中心为\(i\),复杂度就被降到了\(O(n)\)(不会证)

回文自动机能做的事就更多了。它可以统计本质不同的回文子串的个数、每种回文子串的长度和数量、以某个点为结尾的回文串个数等。

在回文自动机中,每个结点表示一个本质不同的回文串。和AC自动机类似,回文自动机有两种边,一种是连向当前回文串在两边加入两个相同字母得到的新回文串,每个点这样的边最多有字符集大小个;另一种是连向该回文串的最长后缀回文串,即\(fail\)指针。

构建回文自动机也比较简单。首先新建两个结点\(0\)和\(1\)分别表示长度为\(2\)和长度为\(1\)的回文串的父节点,前者的\(fail\)指向后者,后者的长度为\(-1\)。每个结点的子结点默认都为\(0\)。接着和AC自动机类似的,每次跳\(fail\)找到以该位置为结尾的最长回文串,如果该回文串是第一次出现再跳\(fail\)找到当前结点的\(fail\)。

那么本质不同的回文子串个数即为\(结点个数-2\),出现次数可以类似于AC自动机的统计方法,最后沿\(fail\)树上传标记。以某个点为结尾的回文串个数即为以该位为结尾的最长回文串在\(fail\)树中的深度。

说点什么

4 评论 在 "Manacher算法&回文自动机"

提醒
排序:   最新 | 最旧 | 得票最多
成员

讲得清楚,条理清晰

成员

厉害

游客

%%%

wpDiscuz