UOJ #103. 【APIO2014】Palindromes (回文自动机模板题)
题意：
给你一个由小写拉丁字母组成的字符串 s。我们定义 s 的一个子串的存在值为这个子串在 s 中出现的次数乘以这个子串的长度。
对于给你的这个字符串 s，求所有回文子串中的最大存在值。
思路：
回文自动机，也叫回文树，但其实并不是树2333,所以以后还是称为回文自动机，缩写为PAM
学会了(?)SAM之后再看PAM真是简单得一逼。
学习笔记之后补。
对于这道题，PAM中一个状态的cnt表示的该状态所表示的回文串出现的次数
len表示的是该状态所表示的回文串的长度
UPDATE:
下面的代码风格太丑了，打算弃用。
更新的代码风格见最后
1#include <iostream>
2#include <cstdio>
3#include <cstring>
4#include <algorithm>
5typedef long long LL;
6#define ri register int
7using namespace std;
8#define MAXALP 30
9#define ms(a,x) memset(a,x,sizeof(a))
10const int N = 3E5+7;
11struct PAM
12{
13 int cnt,len,fail;
14 int nxt[MAXALP];
15}st[N];
16int n, m, sz , last, cur;
17char s[N];
18inline int new_node(int x)
19{
20 st[sz].len = x; st[sz].cnt = 0;
21 ms(st[sz].nxt,0);
22 return sz++;
23}
24inline int get_fail(int x, int n)
25{
26 while(s[n-st[x].len-1] != s[n]) x = st[x].fail;
27 return x;
28}
29inline void pam_init()
30{
31 sz = 0 ;
32 new_node(0);
33 new_node(-1);
34 st[0].fail = 1;
35 ms(st[0].nxt,0);
36 last = 0;
37}
38void pam_insert( int c,int head)
39{
40 cur = get_fail(last,head);
41 if (!st[cur].nxt[c])
42 {
43 int nw = new_node(st[cur].len+2);
44 st[nw].fail = st[get_fail(st[cur].fail,head)].nxt[c];
45 st[cur].nxt[c] = nw;
46 }
47 last = st[cur].nxt[c];
48 st[last].cnt++;
49}
50int main()
51{
52 scanf("%s",s);
53 n = strlen(s);
54 pam_init();
55 for(int i=0;i<n;i++) pam_insert(s[i]-'a',i);
56 for(int i=sz-1;i>=0;i--) st[st[i].fail].cnt += st[i].cnt;
57 LL ans = 0;
58 for(int i=2;i<sz;i++) ans = max(ans, 1LL*st[i].len*st[i].cnt);
59 cout<<ans<<endl;
60 return 0;
61}
62
63
64
65
66
67
68
69
70/* ***********************************************
71Author :111qqz
72Created Time :2017年11月14日 星期二 00时13分44秒
73File Name :103.cpp
74************************************************ */
75
76#include <bits/stdc++.h>
77#define ms(a,x) memset(a,x,sizeof(a))
78typedef long long LL;
79using namespace std;
80const int N=3E5+7;
81struct PAM
82{
83 int fail,cnt,len;
84 int nxt[26];
85}st[N];
86char S[N];
87int n,now,sz;
88void pam_init()
89{
90 st[0].fail = st[1].fail = 1;
91 st[1].len = -1;
92 sz = 1;
93}
94void extend(int c,int pos)
95{
96 int p = now;
97 while (S[pos-st[p].len-1]!=S[pos]) p = st[p].fail;
98 if (!st[p].nxt[c]){
99 int np=++sz,q=st[p].fail;
100 st[np].len=st[p].len+2;
101 while (S[pos-st[q].len-1]!=S[pos]) q=st[q].fail;
102 st[np].fail=st[q].nxt[c];
103 st[p].nxt[c] = np;
104 }
105 now=st[p].nxt[c];
106 st[now].cnt++;
107}
108int main()
109{
110 scanf("%s",S);
111 pam_init();
112 for ( int i = 0 ,_=strlen(S); i < _ ; i++)
113 extend(S[i]-'a',i);
114 LL ans = 0 ;
115 for ( int i = sz ; i >= 1 ; i--)
116 {
117 st[st[i].fail].cnt += st[i].cnt;
118 ans = max(ans,1LL*st[i].len*st[i].cnt);
119 }
120 cout<<ans<<endl;
121 return 0;
122}