题目大意
给出一个只由小写英文字符$a,b,c…y,z$组成的字符串$S$，求$S$中最长回文串的长度。
题目分析
以前用马拉车算法写的，现在用回文自动机写一写。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=300005;
struct Palindsome_Automaton {
int child[maxn][26];
int n,size,last,s[maxn],len[maxn],next[maxn];
Palindsome_Automaton() {init();}
void init() {
size=-1;
newnode(0);
newnode(-1);
last=n=0;
s[0]=-1;
next[0]=next[1]=1;
}
int newnode(int v) {
int now=++size;
memset(child[now],0,sizeof(child[now]));
next[now]=0;
len[now]=v;
return now;
}
void insert(int data) {
s[++n]=data;
int p=last;
while(s[n-len[p]-1]!=s[n])p=next[p];
if(!child[p][data]) {
int now=newnode(len[p]+2),q=next[p];
while(s[n-len[q]-1]!=s[n])q=next[q];
next[now]=child[q][data];
child[p][data]=now;
}
last=child[p][data];
}
void build(string s) {
for(auto x:s)insert(x-'a');
}
} pam;
char s[maxn];
int ans=0;
int main() {
while(~scanf("%s",s)) {
ans=0;
pam.init();
pam.build(s);
for(int i=2; i<=pam.size; i++)ans=max(ans,pam.len[i]);
printf("%d\n",ans);
}
return 0;
}
|
