回文自動機做題技巧

① 靈活利用維護的各個資料：

節點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​​