回文自动机有些很优秀的性质。
广义回文自动机
你现在要对多个串建回文自动机,一个一个直接插进回文自动机里是对的。
(也就是广义后缀自动机假掉的那种建法)
最小回文循环节
事实上就是 border 理论那套。
考虑回文自动机上的一个节点 \(x\),那么他的最小回文循环节长度就是 \(len[x]-len[fail[x]]\)(如果存在)。
存在性也是好判的。
有了这两个性质,它可以很方便地处理一些回文相关的计数题,比如这道题(需要权限)。
标签:Luogu,最小,len,广义,自动机,回文 From: https://www.cnblogs.com/Nesraychan/p/16911069.html