http://uoj.ac/problem/103

题意：

给你一个由小写拉丁字母组成的字符串 s。我们定义 s 的一个子串的存在值为这个子串在 s 中出现的次数乘以这个子串的长度。

对于给你的这个字符串 s，求所有回文子串中的最大存在值。

思路：

回文自动机，也叫回文树，但其实并不是树2333,所以以后还是称为回文自动机，缩写为PAM

学会了(?)SAM之后再看PAM真是简单得一逼。

学习笔记之后补。

对于这道题，PAM中一个状态的cnt表示的该状态所表示的回文串出现的次数

len表示的是该状态所表示的回文串的长度

UPDATE:

下面的代码风格太丑了，打算弃用。

更新的代码风格见最后

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
#define ri register int
using namespace std;
#define MAXALP 30
#define ms(a,x) memset(a,x,sizeof(a)) 
const int N = 3E5+7;
struct PAM
{
    int cnt,len,fail;
    int nxt[MAXALP];
}st[N];
int n, m, sz , last, cur;
char s[N];
inline int new_node(int x)
{
    st[sz].len = x; st[sz].cnt = 0;
    ms(st[sz].nxt,0);
    return sz++;
}
inline int get_fail(int x, int n)
{
    while(s[n-st[x].len-1] != s[n]) x = st[x].fail;
    return x;
}
inline void pam_init()
{
    sz = 0 ;
    new_node(0);
    new_node(-1);
    st[0].fail = 1;
    ms(st[0].nxt,0);
    last = 0;
}
void pam_insert( int c,int head)
{
    cur = get_fail(last,head);
    if (!st[cur].nxt[c])
    {
    int nw = new_node(st[cur].len+2);
    st[nw].fail = st[get_fail(st[cur].fail,head)].nxt[c];
    st[cur].nxt[c] = nw;
    }
    last = st[cur].nxt[c];
    st[last].cnt++;
}
int main()
{
    scanf("%s",s);
    n = strlen(s);
    pam_init();
    for(int i=0;i<n;i++) pam_insert(s[i]-'a',i);
    for(int i=sz-1;i>=0;i--) st[st[i].fail].cnt += st[i].cnt;
    LL ans = 0;
    for(int i=2;i<sz;i++) ans = max(ans, 1LL*st[i].len*st[i].cnt);
    cout<<ans<<endl;
    return 0;
}








/* ***********************************************
Author :111qqz
Created Time :2017年11月14日 星期二 00时13分44秒
File Name :103.cpp
************************************************ */

#include <bits/stdc++.h>
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
using namespace std;
const int N=3E5+7;
struct PAM
{
    int fail,cnt,len;
    int nxt[26];
}st[N];
char S[N];
int n,now,sz;
void pam_init()
{
    st[0].fail = st[1].fail = 1;
    st[1].len = -1;
    sz = 1;
}
void extend(int c,int pos)
{
    int p = now;
    while (S[pos-st[p].len-1]!=S[pos]) p = st[p].fail;
    if (!st[p].nxt[c]){
    int np=++sz,q=st[p].fail;
    st[np].len=st[p].len+2;
    while (S[pos-st[q].len-1]!=S[pos]) q=st[q].fail;
    st[np].fail=st[q].nxt[c];
    st[p].nxt[c] = np;
    }
    now=st[p].nxt[c];
    st[now].cnt++;
}
int main()
{
    scanf("%s",S);
    pam_init();
    for ( int i = 0 ,_=strlen(S); i < _ ; i++)
        extend(S[i]-'a',i);
    LL ans = 0 ;
    for ( int i = sz ; i >= 1 ; i--)
    {
        st[st[i].fail].cnt += st[i].cnt;
        ans = max(ans,1LL*st[i].len*st[i].cnt);
    }
    cout<<ans<<endl;
    return 0;
}