Manacher这个算法学了很久了,一直没有机会验证自己是不是彻底弄明白,今天写篇文章来查缺补漏

约定

下标从0开始计数
回文串:S=S_rev (S_rev是S的反转字符串)

什么是Manacher

一个在线性时间内找到字符串所有位置的回文串大小的算法。

从暴力到线性

O(n^3)

最容易想到的是枚举左右端点,看这个串是不是回文的

1
过于简单不予展示。

O(n^2)

我们知道回文串一定有一个回文中心,它的左右同样位置的字符相等。于是我们可以考虑枚举这个点

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
int n,m,_;
string s;
int d1[maxn];//奇数半径 ans = 2*d1[i]-1
int d2[maxn];//偶数半径 ans = 2*d2[i]
int main()
{
s="abababc";
//s="cbaabd";
n=s.length();

for(int i=0;i<n;i++)
{
//先来求奇数
d1[i]=1;
while( i-d1[i]>=0 && i+d1[i]<n &&s[i-d1[i]] == s[i+d1[i]] )
{
d1[i]++;
}
//偶数
d2[i]=0;
while( i-d2[i]>=0 && i+d2[i]+1<n &&s[i-d2[i]] == s[i+d2[i]+1] )
{
d2[i]++;
}
}
for(int i=0;i<n;i++)
cout<<s[i]<<" ";
cout<<endl;
for(int i=0;i<n;i++)
cout<<d1[i]<<" ";
cout<<endl;
for(int i=0;i<n;i++)
cout<<d2[i]<<" ";
cout<<endl;
return 0;

}

O(n)

现在我们来讲解Manacher算法。
首先,我们知道,偶数情况是可以在奇数情况上做一些修改产生的,于是乎,我们只讨论奇数的情况。
我们先确定两个值l,r。它们是已找到的最靠右边的回文串的边界。简单点就是对于位置i,l和r就是以位置i-1为中心的回文串的边界。i=0时l=0,r=-1。
那么我们怎么利用l,r和之前求好的d1[i]呢?
1’ 如果i在[l,r]这个范围内,很明显有一个对应点 j (r-i=j-l) , 而且这个j点的d1[j]理论上是等于d1[i]的。但是这是有条件的,这个条件是 j-d1[j]+1>=l。如果d1[j]太大了,使得左端点到了l之外,而[l,r]之外的对称性是没有任何保证的(原因有,r=n-1或者是S[l-1]!=S[r+1]),所以此时d1[i]=(r-i+1)。
再从这里开始继续朴素计算。
2’ 如果i不在[l,r]这个范围内,很明显只能朴素计算了。
每次计算完d1[i]后都要更新l,r。

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
int n,m,_;
string s;
int d1[maxn];//奇数半径 ans = 2*d1[i]-1
//只求奇数的,所以删除了d2
int l,r,k;
int main()
{
//s="abababc";
s="cbaabd";
n=s.length();
l=0;
r=-1;
for(int i=0;i<n;i++)
{
//首先就是判断 i 在不在已经求好的回文串里面
if( i > r ) // 不在
{
// 只能使用朴素算法
k=1;
while(i-k>=0 && i+k<n && s[i-k]==s[i+k])
k++;
//结束循环表示k是以i为中心的回文串半径最大值
d1[i]=k;
}
else // 在
{
//去找j
int j=l+r-i;
k=d1[j];
if(i+k<=r)//再来看以j为中心的回文串的左边对应 到i的右边后有没有超过r
{
//啥事也不发生
k=k;
}
else
{
//超过了,又有谁能保证r之后的事情呢?
//所以k要缩小,缩小到 以i为中心的回文串的右边恰好是r,这个 i+k = r+1
k=(r-i)+1;
}
//接下来就是朴素算法的匹配
while(i-k>=0 && i+k<n && s[i-k]==s[i+k])
k++;
//结束循环表示k是以i为中心的回文串半径最大值
d1[i]=k;
}
//不管如何,我们都要更新l和r
//注意 l 和 r 是边界
l=i-k+1;
r=i+k-1;
}
for(int i=0;i<n;i++)
cout<<s[i]<<" ";
cout<<endl;
for(int i=0;i<n;i++)
cout<<d1[i]<<" ";
cout<<endl;

return 0;
}

什么?你问我偶数怎么改?我已经被偶数的中心点选取绕懵了,但是我可以将任意字符串的长度变为奇数。
对于一个长度为n的字符串,给它的n+1个空位加上一个#字符变为一个长度为2n+1的字符串#S[0]#S[1]#……#S[n-1]# 。
又因为d1[i]表示的是以i为中心的回文串的半径长度。所以答案是2*d1[i]-1。但是由于我们在这里增加了#字符填充。所以d[i]都变成原来长度的一倍了,所以答案是d1[i]-1。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e7+7;
const ll mod= 1e9+7;
int n,m,_;
char s[maxn],ss[maxn];
int d1[maxn];//奇数半径 ans = 2*d1[i]-1
//只求奇数的,所以删除了d2
int l,r,k,ans;
int cnt=0;
int main()
{
scanf("%s",s);
n=strlen(s);
ss[cnt++]='#';
for(int i=0;i<n;i++)
{
ss[cnt++]=s[i];
ss[cnt++]='#';
}
strcpy(s,ss);
n=strlen(s);
l=0;
r=-1;
for(int i=0;i<n;i++)
{
//首先就是判断 i 在不在已经求好的回文串里面
if( i > r ) // 不在
{
// 只能使用朴素算法
k=1;
while(i-k>=0 && i+k<n && s[i-k]==s[i+k])
k++;
//结束循环表示k是以i为中心的回文串半径最大值
d1[i]=k;
}
else // 在
{
//去找j
int j=l+r-i;
k=d1[j];
if(i+k<=r)//再来看以j为中心的回文串的左边对应 到i的右边后有没有超过r
{
//啥事也不发生
k=k;
}
else
{
//超过了,又有谁能保证r之后的事情呢?
//所以k要缩小,缩小到 以i为中心的回文串的右边恰好是r,这个 i+k = r+1
k=(r-i)+1;
}
//接下来就是朴素算法的匹配
while(i-k>=0 && i+k<n && s[i-k]==s[i+k])
k++;
//结束循环表示k是以i为中心的回文串半径最大值
d1[i]=k;
}
//不管如何,我们都要更新l和r
//注意 l 和 r 是边界
l=i-k+1;
r=i+k-1;
}
for(int i=0;i<n;i++)
{
ans=max(ans,d1[i]);
}
printf("%d\n",ans-1);
return 0;

}