【模板】Manacher 算法


题目链接:Luogu P3805 【模板】manacher算法

代码:

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
#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;
char s[30000000];
int res[30000000];
int main() {
char ch;
int nowm = 1, nowr = 1, len = 1, ans = 0;
s[len] = '~', res[len] = 1;
while (isalpha(ch=getchar()))
s[++len] = ch, s[++len] = '~';
for (int i = 2; i <= len; ++i) {
if (i <= nowr)
res[i] = min(res[(nowm<<1)-i], ((nowr-i)<<1)+1);
else res[i] = 1;
int l = (res[i]>>1)+1;
while (i+l <= len && i-l
&& s[i+l] == s[i-l])
l++,
res[i] += 2;
if (nowr < i+l-1)
nowr = i+l-1,
nowm = i;
}
for (int i = 1; i <= len; ++i)
ans = max(ans, res[i]);
printf("%d", ans>>1);
return 0;
}

 评论