P3649
第一次對于回文樹的運用。
一道回文樹的模闆題,我們最後隻需要統計一下回文樹中每個串的出現次數乘以每個串的不同串的個數。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
//#include <unordered_map>
//#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 3e5 + 7, maxM = 26;
int N;
struct Palindromic_Tree
{
int next[maxN][maxM] ;//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 < maxM ; ++ 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 ) ;//通過上一個回文串找這個回文串的比對位置
if ( !next[cur][c] )
{//如果這個回文串沒有出現過,說明出現了一個新的本質不同的回文串
int now = newnode ( len[cur] + 2 ) ;//建立節點
fail[now] = next[get_fail ( fail[cur] )][c] ;//和AC自動機一樣建立fail指針,以便失配後跳轉
next[cur][c] = now ;
num[now] = num[fail[now]] + 1 ;
}
last = next[cur][c] ;
cnt[last] ++ ;
}
void count ()
{
for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
//父親累加兒子的cnt,因為如果fail[v]=u,則u一定是v的子回文串!
}
} pam;
char s[maxN];
int main()
{
pam.init();
scanf("%s", s + 1);
N = (int)strlen(s + 1);
for(int i=1; i<=N; i++)
{
pam.add(s[i]);
}
pam.count();
ll ans = 0;
for(int i=2; i<=pam.p; i++)
{
ans = max(ans, 1LL * pam.cnt[i] * pam.len[i]);
}
printf("%lld\n", ans);
return 0;
}