O(n)时间复杂度求字符串的最大回文子串 相关题目:【模板】manacher算法

Manacher算法 - 经典算法与数据结构

题目描述

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.

字符串长度为n

输入输出格式

输入格式: 一行小写英文字符a,b,c...y,z组成的字符串S

输出格式: 一个整数表示答案

输入样例

aaa

输出样例#1:

3

AC代码

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
#include <cstdio>
#include <cstring>
#define re register int
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

char s[11000020];
int h[11000020], n;

int manacher() {
s[0]='$', s[n+1]='#';
int id, mx = 0, num = 0;

for(re i = 1 ; i <= n ; i++) {
if(i < mx)
h[i] = min(mx-i+1, h[id*2-i]);
else h[i] = 1;

while(s[i+h[i]]==s[i-h[i]]) h[i]++;
if(i+h[i]-1 > mx)
mx = i+h[i]-1, id = i;
num = max(num, h[i]*2-1);
}
mx = 0;
for(re i = 1 ; i <= n ; i++) {
if(i < mx)
h[i] = min(mx-i, h[id*2-i]);
else h[i] = 0;

while(s[i+h[i]+1]==s[i-h[i]]) h[i]++;
if(i+h[i] > mx)
mx = i+h[i], id = i;
num = max(num, h[i]*2);
}
return num;
}

int main() {
scanf("%s", s+1);
n = strlen(s+1);
printf("%d\n", 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
31
32
33
34
35
36
37
38
// luogu-judger-enable-o2
#include <cstdio>
#include <cstring>
#include <cctype>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
#define drep(i,a,b) for(re i=(a);i>=(b);--i)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

int n, ans=0;
int mx=0, mid=0, p[22000020];
char s[22000020];

int manacher() {
int len=0;
rep(i,1,n) {
if(i < mx)
p[i] = min(p[mid*2-i], mx-i);
else p[i] = 1;

while(s[i+p[i]]==s[i-p[i]]) p[i]++;
if(p[i]+i > mx)
mx = p[i]+i, mid = i;
len = max(len, p[i]-1);
}
return len;
}

int main() {
scanf("%s", s+1); s[0] = '#';
n = strlen(s+1);
drep(i,n,1) s[i*2] = s[i];
s[1] = '#'; rep(i,1,n) s[i*2+1] = '#';
n = n*2+1;

printf("%d\n", manacher());
}