回文自动机

学习了一种对付回文问题的一个强有力的工具,回文自动机,和manecher功能是一样的,但是会更加的强大好用,就像ac自动机会比kmp强大,后缀自动机会比后缀数组强大是一个道理。

之前也学习了不同类型的自动机,总的来说自动机需要很好的理解本质,没了本质寸步难行。自动机中最重要的就是状态,要深刻的理解自动机节点的状态表示的是什么含义,不过有时候状态可能并没有具体的意义,但是可以含糊的认为表示某个类型的集合。

那么开始回文自动机的学习。

首先介绍下一篇写的比较好的博客:回文树【处理一类回文串问题的强力工具】 by 鸟神

普遍是叫它回文树,其实这个数据结构就是一种回文自动机,但每个节点只有一个父亲,所以可以认为是一颗回文树,事实上这个和后缀自动机是有异曲同工之妙的,既可以作为树来用也可以作为自动机来搞。

自动机有个好有趣的功能,可以通过拓扑来得到某种状态集合的一些属性值,回文自动机同理。回文自动机的cnt[i]统计的就是状态i本质不同回文的个数,len[i]表示的是状态i最大回文长度,那么状态i的属性就可以表示成 { len[i], cnt[i] }, 尤其是统计个数的属性可以通过拓扑来得到,类似在自动机上dp。

鸟神的博客已经将自动机将的很清楚了,我就不累赘了,我来谈谈自动机和其等价的数组结构。manacher,和回文自动机是可以等价使用的,数组类的数据结构往往处理一些问题比较精简,代码量小,自动机类的数据结构往往处理统计个数的问题十分的容易,因为自动机的状态转移就是统计的一个很好的工具,可以认为是在自动机上dp并且转移。熟练掌握自动机和数组类的数据结构对处理字符串问题有着全面的保证。

补充下对“状态i表示的回文”的理解,当进一步理解回文自动机应该会明白本质不同的回文子串个数是线性的,最多只会有n个(n表示字符串的长度),那么一个状态表示的回文的含义:以当前状态i结尾的回文有多个,但是此状态只表示最长的一个,因为比较短的一定在之前的状态中被表示过了,因此一个状态就独一无二的表示这一个本质不同的回文子串。进一步理解可以看代码注释!

回文自动机的代码:

 

LEAVE A COMMENT