回文樹(回文自動機) - BZOJ 3676 回文串 BZOJ 3676 回文串 Problem's Link: http://www.lydsy.com/JudgeOnline/problem.php?id=3676

Mean: 

略

analyse:

由于構造完回文自動機後，len[i]表示第i個回文串的長度，cnt[i]表示第i個回文串出現的次數，隻需兩者相乘去最大就可。

注意：i是從2開始，因為有兩個長度為0和長度為-1的節點。

Time complexity: O(N)

Source code: 

/*

* this code is made by crazyacking

* Verdict: Accepted

* Submission Date: 2015-08-19-13.56

* Time: 0MS

* Memory: 137KB

*/

#include <queue>

#include <cstdio>

#include <set>

#include <string>

#include <stack>

#include <cmath>

#include <climits>

#include <map>

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#define  LL long long

#define  ULL unsigned long long

using namespace std;

const int MAXN = 300005 ;

const int N = 26 ;

char s[MAXN];

struct Palindromic_Tree

{

     int next[MAXN][N] ;//next指針，next指針和字典樹類似，指向的串為目前串兩端加上同一個字元構成

     int fail[MAXN] ;//fail指針，失配後跳轉到fail指針指向的節點

     int cnt[MAXN] ;

     int num[MAXN] ;

     int len[MAXN] ;//len[i]表示節點i表示的回文串的長度

     int S[MAXN] ;//存放添加的字元

     int last ;//指向上一個字元所在的節點，友善下一次add

     int n ;//字元數組指針

     int p ;//節點指針

     int newnode(int l)     //建立節點

     {

           for(int i = 0 ; i < N ; ++ i) next[p][i] = 0 ;

           cnt[p] = 0 ;

           num[p] = 0 ;

           len[p] = l ;

           return p ++ ;

     }

     void init()   //初始化

           p = 0 ;

           newnode(0) ;

           newnode(-1) ;

           last = 0 ;

           n = 0 ;

           S[n] = -1 ;//開頭放一個字元集中沒有的字元，減少特判

           fail[0] = 1 ;

     int get_fail(int x)     //和KMP一樣，失配後找一個盡量最長的

           while(S[n - len[x] - 1] != S[n]) x = fail[x] ;

           return x ;

     void add(int c)

           c -= 'a' ;

           S[++ n] = c ;

           int cur = get_fail(last) ;   //通過上一個回文串找這個回文串的比對位置

//            cout<<cur<<endl;

           if(!next[cur][c])     //如果這個回文串沒有出現過，說明出現了一個新的本質不同的回文串

           {

                 int now = newnode(len[cur] + 2) ;   //建立節點

//                  cout<<get_fail(fail[cur])<<endl;

                 fail[now] = next[get_fail(fail[cur])][c] ;   //和AC自動機一樣建立fail指針，以便失配後跳轉

//                  cout<<fail[now]<<endl;

                 next[cur][c] = now ;

                 num[now] = num[fail[now]] + 1 ;

           } last = next[cur][c] ;

//            cout<<last<<endl;

           cnt[last] ++ ;

     void count()

           for(int i = p - 1 ; i >= 0 ; -- i) cnt[fail[i]] += cnt[i] ;

           //父親累加兒子的cnt，因為如果fail[v]=u，則u一定是v的子回文串！

} run;

int main()

     scanf("%s",&s);

     int n=strlen(s);

     run.init();

     for(int i=0; i<n; i++) run.add(s[i]);

     run.count();

     LL ans=LLONG_MIN;

     for(int i=2; i<run.p; ++i)

           ans=max(ans,(LL)run.cnt[i]*run.len[i]);

     cout<<ans<<endl;

     return 0;

}