bzoj3676 [Apio2014]迴文串

NO IMAGE

Description


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

一個串是迴文的,當且僅當它從左到右讀和從右到左讀完全一樣。
資料滿足1≤字串長度≤300000。

Solution


第一次接觸,嚇得我趕緊學習一波
具體就是每個節點記錄長度,x向y連邊權為w表示x通過首尾新增一個字元w能得到迴文串y
與ac自動機類似的,用一個fail記錄最長同字尾的迴文串。一個比較神奇的操作就是建兩個點長度為0、-1來表示奇偶性不同的迴文串
需要注意的是統計的時候不能漏一個迴文串包含另一個迴文串的情況

Code


#include <stdio.h>
#include <string.h>
#include <algorithm>
#define rep(i,st,ed) for (int i=st;i<=ed;  i)
#define drp(i,st,ed) for (int i=st;i>=ed;--i)
typedef long long LL;
const int N=300005;
char st[N];
struct pam {
    int last,cnt,fail[N],rec[N][26],len[N],size[N];
    pam() {len[1]=-1; fail[0]=fail[1]=1; cnt=1;}
    void ins(int x,int n) {
        int p=last;
        while (st[n-len[p]-1]!=st[n]) p=fail[p];
        if (!rec[p][x]) {
            int now=  cnt,k=fail[p]; len[now]=len[p] 2;
            while (st[n-len[k]-1]!=st[n]) k=fail[k];
            fail[now]=rec[k][x]; rec[p][x]=now;
        }
        last=rec[p][x];
        size[last]  ;
    }
    void solve() {
        LL ans=0;
        drp(i,cnt,1) {
            size[fail[i]] =size[i];
            ans=std:: max(ans,(LL)size[i]*len[i]);
        }
        printf("%lld\n", ans);
    }
}pam;
int main(void) {
    // freopen("palindrome.in","r",stdin);
    // freopen("palindrome.out","w",stdout);
    scanf("%s",st 1);
    int len=strlen(st 1);
    rep(i,1,len) {
        pam.ins(st[i]-'a',i);
    }
    pam.solve();
    return 0;
}