回文自动机做题技巧

① 灵活利用维护的各个数据：

节点x
len[x]表示该节点表示的字符串的最长长度
fail[x]指向的节点表示的字符串是节点x表示字符串的最长子回文串
cnt[x]在经过以下处理后表示在s中该节点所表示字符串在s中的出现次数
for(int i=sz;i>=0;++i)
  cnt[fail[i]]+=cnt[i];      

例题：​​P1659 [国家集训队]拉拉队排练​​

② 将​

​fail​

​​数组与​

​len​

​​数组相结合，可以得出更多的信息，​

​fail​

​数组指向的是该节点、对应子串的最长回文后缀，那么利用这两个信息，就可以得出最长回文后缀与母串之间的长度关系。

例题：​​P4287 [SHOI2011]双倍回文​​

③如果题目要求找到两个连续的回文串，可以考虑建两个回文自动机，一个顺序一个逆序

例题：​​P4555 [国家集训队]最长双回文串​​

④将 dp 与回文自动机相结合

例题：​​P4762 [CERC2014]Virus synthesis​​