哦也！偉大的回文樹（回文自動機）！

例題引入

例題引入：洛谷P3649

話說馬上就要APIO了，litble去看了看曆年的APIO題……發現這道題用回文樹非常好做，是以就去學了一下回文樹。

所謂回文樹，就是每個節點代表一個不同的回文串的一種資料結構。

它也有可以類比于AC自動機的fail指針，表示失配了之後去尋找哪個節點。

此外，每個節點上還要記錄

len:該節點代表的回文串長度

cnt:該節點代表的回文串在原串中出現的次數(然而在建立的過程中這個求不完全，還要再跑一遍count函數去求，這就是後話了)

為了輔助比對，再弄一個s，表示目前插入到回文樹裡的字元。 s0=−1 s 0 = − 1 （一個不可能出現的字元）

初始化

一開始回文樹上有兩個節點,0和1。0是輔助處理偶數回文串的，1是輔助處理奇數回文串的。 fail(0)=1 f a i l ( 0 ) = 1 ，因為顯然一個新加的字元不能去組成一個長度為2偶數回文串，還可以組成一個長度為1的奇數回文串。 len(1)=−1,len(0)=0 l e n ( 1 ) = − 1 , l e n ( 0 ) = 0 ，因為每一次添加的新節點的len顯然是其父節點+2，是以奇數回文串要事先減1。

比對

我們加入了一個字元x，需要尋找加入這個字元後可以形成的新回文串，這個回文串應該長這樣：

x 某一個原本存在的回文串 x

是以比對方式如下：

int find(int x) {
    while(s[n-len[x]-]!=s[n]) x=fail[x];
    return x;
}
           

插入

記last為上一次插入後對應的節點，也就是以上一個插入的字元結尾的最長回文串代表的節點。

首先順着last的fail指針找一個比對了了的節點。

然後xjb操作一通，方法如下（應該能看懂……吧?）

void add(int t) {
    s[++n]=t;int cur=find(last);
    if(!ne[cur][t]) {//ne:兒子
        fail[++SZ]=ne[find(fail[cur])][t];
        ne[cur][t]=SZ,len[SZ]=len[cur]+;//注意這句在後，以免影響find的過程
    }
    last=ne[cur][t],++cnt[last];
}
           

統計答案

也就是傳說中的count函數啦！我們可以把cnt完善一下：

LL count() {//typedf long long LL;
    LL re=;
    for(RI i=SZ;i>=;--i) {
        cnt[fail[i]]+=cnt[i];
        if(L*cnt[i]*len[i]>re) re=L*cnt[i]*len[i];
    }
    return re;
}
           

完整代碼

最後獲得該題的完整代碼：

#include<bits/stdc++.h>
using namespace std;
const int N=;
#define RI register int
typedef long long LL;
struct orzabs{
    int last,n,SZ;
    int ne[N][],fail[N],cnt[N],len[N],s[N];
    void init() {SZ=,len[]=-,s[]=-,fail[]=;}
    int find(int x) {
        while(s[n-len[x]-]!=s[n]) x=fail[x];
        return x;
    }
    void add(int t) {
        s[++n]=t;int cur=find(last);
        if(!ne[cur][t]) {
            fail[++SZ]=ne[find(fail[cur])][t];
            ne[cur][t]=SZ,len[SZ]=len[cur]+;
        }
        last=ne[cur][t],++cnt[last];
    }
    LL count() {
        LL re=;
        for(RI i=SZ;i>=;--i) {
            cnt[fail[i]]+=cnt[i];
            if(L*cnt[i]*len[i]>re) re=L*cnt[i]*len[i];
        }
        return re;
    }
}T;
char s[N];int slen;
int main()
{
    scanf("%s",s),slen=strlen(s);
    T.init();
    for(RI i=;i<slen;++i) T.add(s[i]-'a');
    printf("%lld\n",T.count());
    return ;
}
           

習題

ural1960 Palindromes and Super Abilities

bzoj2160 拉拉隊排練

bzoj2565 最長雙回文串