隐藏
Manacher算法笔记 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

Manacher算法笔记

前天在做一道回文自动机题的时候,发现自己不会写Manacher了。于是重新学了一遍。
话不多说,直接贴链接,讲得很好我也就没什么要补充的了。

另外,时间复杂度显然是$O(n)$的。

下面是 HDU3068最长回文 的代码:

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
#include<bits/stdc++.h>

using namespace std;

const int maxn=110005*2;

char tmp[maxn];
int n,f[maxn];
string s;

int main() {
while(~scanf("%s",tmp)) {
int len=strlen(tmp);
s.clear();
s.push_back('#');
for(int i=0; i<len; i++)s.push_back(tmp[i]),s.push_back('#');
n=s.length();
int Max=0,id=0,ans=0;
for(int i=1; i<=n-2; i++) {
f[i]=Max>i?min(f[2*id-i],Max-i):1;
while(i-f[i]>=0&&i+f[i]<n&&s[i-f[i]]==s[i+f[i]])f[i]++;
if(f[i]+i>Max) {Max=f[i]+i;id=i;}
ans=max(ans,f[i]-1);
}
printf("%d\n",ans);
}
return 0;
}

姥爷们赏瓶冰阔落吧~