Manacher算法模板

描述

参考资料:

Manacher算法 - 经典算法与数据结构 - SegmentFault 思否

hdu3068之manacher算法+详解

代码

头部

1
2
3
4
5
6
#include <cstring>
#include <algorithm>

const int N = 1e5+10;
char s[N],s_new[N*2];
int p[N*2];

初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int Init()
{
int len = strlen(s);
s_new[0] = '$';
s_new[1] = '#';
int j = 2;

for(int i = 0;i < len;i++)
{
s_new[j++] = s[i];
s_new[j++] = '#';
}

s_new[j] = '\0';

return j; // 返回 s_new 的长度
}

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
int Manacher()
{
int len = Init(); // 取得新字符串长度并完成向 s_new 的转换
int max_len = -1; // 最长回文长度

int id;
int mx = 0;

for(int i = 1;i < len;i++)
{
if(i < mx)
p[i] = min(p[2*id-i],mx-i);
else
p[i] = 1;

while(s_new[i-p[i]] == s_new[i+p[i]]) // 不需要边界判断,因为有"$"、"\0"
p[i]++;

// 每走一步都要用i和mx比较
if(mx < i+p[i])
{
id = i;
mx = i+p[i];
}
max_len = max(max_len,p[i]-1);
}
return max_len;
}