UOJ #103:【APIO2014】Palindromes
题意：
考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出
现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最
大出现值。
学会马拉车之后发现还需要后缀数组才能AC这题，拒绝。。。。
于是get一发回文树(回文自动机)技巧，看完：（http://blog.csdn.net/lwfcgz/article/details/48739051)感觉还是挺simple的
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 310010 10 #define llg int 11 #define RG register int 12 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 13 llg n,m,tot,cnt[maxn],len[maxn],fail[maxn],last,son[maxn][27],cur; 14 char s[maxn]; 15 long long ans; 16 17 inline llg new_(RG x) 18 { 19 len[tot]=x; cnt[tot]=0; 20 return tot++; 21 } 22 23 inline llg get_fail(RG x,RG n) 24 { 25 while (s[n-len[x]-1]!=s[n]) x=fail[x]; 26 return x; 27 } 28 29 inline void init() 30 { 31 scanf("%s",s+1); 32 n=strlen(s+1); 33 new_(0),new_(-1); 34 fail[0]=1,last=0; 35 } 36 37 int main() 38 { 39 yyj("Palindromes"); 40 init(); 41 for (RG i=1;i<=n;i++) 42 { 43 RG x=s[i]-'a'; 44 cur=get_fail(last,i); 45 if (!son[cur][x]) 46 { 47 RG nw=new_(len[cur]+2); 48 fail[nw]=son[get_fail(fail[cur],i)][x]; 49 son[cur][x]=nw; 50 } 51 last=son[cur][x]; 52 cnt[last]++; 53 } 54 for (llg i=tot-1;i>=0;i--) cnt[fail[i]]+=cnt[i]; 55 for (llg i=2;i<tot;i++) ans=max(ans,(long long )len[i]*cnt[i]); 56 cout<<ans; 57 return 0; 58 }