题目描述

给我们一个字符串S,定义S的子串的价值为该子串在S中的出现次数*该字串的长度.
求该字符串S的所有回文子串的最大值.

样例

输入

abacaba

输出

7

分析

PAM上每个节点维护一个cnt表示该节点的出现次数,最后求一下每个节点的cnt*len,取最大值即可.

PAM

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
int tr[N][26],idx,last,tot;
int len[N];
long long cnt[N];
int fail[N];
char s[N];
int ans;
int node(int x){
    len[idx++]=x;
    return idx-1;
}
void init(){
    idx=tot=0;
    node(0);
    node(-1);
    fail[0]=1,fail[1]=0;
    last=0;
}
int get_fail(int x){
    while(s[tot-len[x]-1]!=s[tot]){
        x=fail[x];
    }
    return x;
}
void insert(char c){
    tot++;
    int now=get_fail(last);
    if(!tr[now][c-'a']){
        int x=node(len[now]+2);
        int t=get_fail(fail[now]);
        fail[x]=tr[t][c-'a'];
        tr[now][c-'a']=x;

    }
    last=tr[now][c-'a'];
    cnt[last]++;
}

int main(){
    cin>>s+1;
    init();
    for(int i=1;s[i];i++){
        insert(s[i]);
    }
    long long ans=0;
    for(int i=idx-1;i>1;i--)cnt[fail[i]]+=cnt[i];
    for(int i=2;i<idx;i++)ans=max(ans,cnt[i]*len[i]);
    cout<<ans;
    return 0;
}