https://vjudge.net/problem/HYSBZ-3676
题意
考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出
现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最
大出现值。
分析
回文树模板题
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(a, b) memset(a, b, sizeof(a))
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
//#define eps 0.0000000001
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define random(a, b) rand()*rand()%(b-a+1)+a
#define pi acos(-1)
//const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5 + ;
const int maxm = +;
const int mod = ; struct PAM{
int nxt[maxn][];
int fail[maxn];
int cnt[maxn];
int num[maxn];
int len[maxn];
int s[maxn];
int last,n,p; int newnode(int w){
for(int i=;i<;i++) nxt[p][i]=;
num[p]=cnt[p]=;
len[p]=w;
return p++;
}
void init(){
n=last=p=;
newnode();
newnode(-);
s[n]=-;
fail[]=;
}
int get_fail(int x){
while(s[n-len[x]-]!=s[n]) x=fail[x];
return x;
}
void add(int c){
c-='a';
s[++n]=c;
int cur=get_fail(last);
if(!nxt[cur][c]){
int now=newnode(len[cur]+);
fail[now]=nxt[get_fail(fail[cur])][c];
nxt[cur][c]=now;
num[now]=num[fail[now]]+;
}
last=nxt[cur][c];
cnt[last]++;
}
void Count(){
for(int i=p-;i>=;i--) cnt[fail[i]]+=cnt[i];
}
};
char s[maxn];
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
// freopen("input.txt", "w", stdout);
#endif
scanf("%s",s);
int len=strlen(s);
PAM pam;
pam.init(); for(int i=;i<len;i++) pam.add(s[i]);
ll ans=;
pam.Count();
for(int i=;i<pam.p;i++) ans=max((ll)pam.cnt[i]*pam.len[i],ans);
printf("%lld\n",ans);
return ;
}