BZOJ3676 [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。

PAM太神了！！！！！！！！！！！！！！！！！！！！！！！！！！！！

http://blog.csdn.net/u013368721/article/details/42100363

#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#define rep(s,t) for(int i=s;i<=t;i++)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
const int maxn=300010;
char ch[maxn];
struct PAM {
    int cnt,last;
    int to[maxn][26],f[maxn],l[maxn],size[maxn];
    PAM() {cnt=1;f[0]=f[1]=1;l[1]=-1;}
    void extend(int c,int n) {
        int p=last;
        while(ch[n-l[p]-1]!=ch[n]) p=f[p];
        if(!to[p][c]) {
            int np=++cnt,k=f[p];
            l[np]=l[p]+2; 
            while(ch[n-l[k]-1]!=ch[n]) k=f[k];
            f[np]=to[k][c];to[p][c]=np;
        }
        size[last=to[p][c]]++;
    }
    long long solve() {
        long long ans=0;
        for(int i=cnt;i;i--) size[f[i]]+=size[i],ans=max(ans,(long long)l[i]*size[i]);
        return ans;
    }
}sol;
int main() {
    scanf("%s",ch+1);int n=strlen(ch+1);
    rep(1,n) sol.extend(ch[i]-'a',i);
    printf("%lld
",sol.solve());
    return 0;
}

View Code