BZOJ [3676: [Apio2014]回文串]

題意：

考慮一個隻包含小寫拉丁字母的字元串s。我們定義s的一個子串t的“出現值”為t在s中的出現次數乘以t的長度。請你求出s的所有回文子串中的最大出現值。

題解：

回文自動機水題，注意插入字元時求出的cnt數組并不是最後的出現次數，而應該還要加上以它為字尾的回文，也就是所有fail指向它的節點的貢獻。

A C AC AC代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 3e5+50;
char s[MAXN];
struct Trie{
    int nxt[MAXN][26],fail[MAXN],len[MAXN],cnt[MAXN];
    int sz,lst;
    inline void Init(){
        fail[0] = fail[1] = 1;
        len[0] = 0,len[1] = -1;
        sz = lst = 1;
        s[0] = '#';
    }
    inline void Insert(char ch,int en){
        int root = lst;
        while(s[en]!=s[en-len[root]-1]) root = fail[root];
        if(!nxt[root][ch-'a']){
            len[++sz] = len[root] + 2;
            int tmp = fail[root];
            while(s[en]!=s[en-len[tmp]-1]) tmp = fail[tmp];
            fail[sz] = nxt[tmp][ch-'a'];
            nxt[root][ch-'a'] = sz;
        }
        lst = nxt[root][ch-'a'];
        cnt[lst]++;
    }
    inline void Solve(){
        LL res = 0;
        for(int i=sz;i>=2;i--) cnt[fail[i]] += cnt[i];
        for(int i=2;i<=sz;i++)
            res = max(res,1LL*len[i]*cnt[i]);
        printf("%lld\n",res);
    }
}PAM;
int main(){
    scanf("%s",s+1);
    PAM.Init();
    for(int i=1;s[i];i++) PAM.Insert(s[i],i);
    PAM.Solve();
    return 0;
}