bzoj 3676: [Apio2014]回文串

Description

考慮一個隻包含小寫拉丁字母的字元串s。我們定義s的一個子串t的“出

現值”為t在s中的出現次數乘以t的長度。請你求出s的所有回文子串中的最

大出現值。

Input

輸入隻有一行，為一個隻包含小寫字母(a -z)的非空字元串s。

Output

輸出一個整數，為逝查回文子串的最大出現值。

Sample Input

【樣例輸入l】

abacaba

【樣例輸入2]

www

Sample Output

【樣例輸出l】

7

【樣例輸出2]

4

HINT

一個串是回文的，當且僅當它從左到右讀和從右到左讀完全一樣。

在第一個樣例中，回文子串有7個：a，b，c，aba，aca，bacab，abacaba，其中：

● a出現4次，其出現值為4：1：1=4

● b出現2次，其出現值為2：1：1=2

● c出現1次，其出現值為l：1：l=l

● aba出現2次，其出現值為2：1：3=6

● aca出現1次，其出現值為1=1：3=3

●bacab出現1次，其出現值為1：1：5=5

● abacaba出現1次，其出現值為1：1：7=7

故最大回文子串出現值為7。

【資料規模與評分】

資料滿足1≤字元串長度≤300000。

思路

這個題求得是 回文串出現次數 * 回文串的長度。

裸的回文串自動機。

len 就是回文串的長度。

cnt 就是回文串出現的次數，

乘起來就好了。

最後注意一下long long 就好了。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+1000;
int Next[N][30],Fail[N],len[N];
int s[N],last,n,p,num[N],cnt[N],sum[N];
int s1[N],s2[N];

// Fail 失配指針。像AC自動機差不多的失配指針，這個指向的是同樣回文串結尾的最長回文串。
// len 目前回文串的長度。 
// s[] 一個個加入新的字母。 
// n 目前加入的是第幾個字元。 
// p 目前是第幾個節點。
// num[i]  代表 i 這個節點所代表的回文串中有多少個本質不同的回文串。 
// cnt[i]  代表 i 這個節點所代表的回文串一共出現了多少次。 這個最後要 count() 一下。

int newnode(int x){  //新加一個節點。
	for (int i = 0; i < 30; i++)
		Next[p][i] = 0;    //加上  i 這個字母可以到達的後繼節點。
	cnt[p] = num[p] = 0;
	len[p] = x;
	return p++;
}
void init(){ // 初始化，首先要見兩個點，偶數節點，和奇數節點。 
	p = 0;
	newnode(0); newnode(-1);
	last = 0, n = 0;
	s[n] = -1; Fail[0] = 1;
	return;
}
int getfail(int x){
	while(s[n-len[x] - 1] != s[n]) x = Fail[x];  //找到滿足的點。 
	return x;
}

int add(int c){
	c -= 'a';
	s[++n] = c;
	int cur = getfail(last);
	if (!Next[cur][c]){ //如果沒有後繼節點。新加入一個節點。
		int now = newnode(len[cur] + 2);
		Fail[now] = Next[getfail(Fail[cur])][c];
		Next[cur][c] = now;
		num[now] = num[Fail[now]] + 1;  //
	}
	last = Next[cur][c];
	cnt[last]++;
	return len[last];
}
void count(){ // count() 最後計算 cnt[] 
	for (int i = p - 1; i >= 0; --i)
		cnt[Fail[i]] += cnt[i];
}
int main(){
	char t[N];
	int ll;
	scanf("%s",t);
	ll = strlen(t);
	long long Max = 0;
	init(); 
	for (int i = 0; i < ll; i++)
		s1[i] = add(t[i]);
	count();
	for (int i = 0; i < p; i++)
		Max = max(Max,1ll*len[i]*cnt[i]);
	printf("%lld\n",Max);
	return 0;
}