算法学习:马拉车算法

算法学习:马拉车算法

学习自博客:

马拉车算法(音译,Manacher’s algorithm)是一个复杂度为 $O(n)$ 的、求一个字符串最长回文子序列的算法。

回文字符串,就是指无论从左向右读还是从右向左读结果都是一样的字符串。如字符串google的最长回文字串为goog

极限暴力的求得字符串最长回文字序列的方法都是寻找每个中心点开始向两边扩延一位一位地看是否相同,这样的算法复杂度回到 $O(n^2)$,显然不满足一般的需求。且由于回文字符串长度的奇偶问题,还需要特别的奇偶分类问题:如回文字符串aba的中心是b这个字母,回文字符串abba的中心是两个b之间。这两种情况需要分别考虑。

马拉车算法思想

去除字符串长度奇偶分类的问题

马拉车首先在每两个字符之间(包括首尾两端)插入一个原字符串没有的特殊符号,比如#。假设我们现在的字符串为google,插入#后便转换为了:#g#o#o#g#l#e#。设字符串长度为 $len$,加入的特殊字符个数一定为 $len + 1$,而 $len$ 与 $len + 1$ 中必为一奇一偶,所以结果一定是一个奇数,这样的话部分回文字符串(如#g#o#o#g#)的中心一定会是一个字符而不是两字符中间。

半径数组

设原来的字符串为 $str$,加上特殊字符处理后的字符串为$strM$。为了记录每一位对应的最长回文字串半径,我们引入与 $strM$ 半径数组 $p[]$,其中 $p[i]$ 表示以 $strM[i]$ 为中心的最长回文字串的半径,如果 $p[i] = 1$ 就说明该回文串就是 $strM[i]$ 本身。如例子#g#o#o#g#l#e#,可得到如下表格:

$i$ 0 1 2 3 4 5 6 7 8 9 10 11 12
$strM[i]$ # g # o # o # g # l # e #
$p[i]$ 1 2 1 2 5 2 1 2 1 2 1 2 1

可以观察到,$p[i] - 1$ 就是以第 $i$ 位为中心的回文字串在原字符串中的长度。假设在原字符串中,该回文字符串的长度 $l$,由于加入了 $l+ 1$ 个#,在新字符串中的长度就会变为 $ln = 2 \times l + 1$。而 $p[i]$ 存储的是新的字符串的回文字串的半径,也就是 $\frac{ln + 1}{2}$ $=$ $l + 1$,即 $p[i] = l + 1$,所以最终结果为 $p[i] - 1$。

由于字符串的最开始与最后都有一个#字符,为了在搜索回文字串时避免总是判断是否越界,我们在字符串的左端与右端都加上另外一个特殊字符,如$^。(其实最后一位处不需要加上这个特殊字符,因为字符串的最后本来就是有一位\0用以标记字符串的结束的。)

所以这个算法的重点就在于如何计算数组 $p[]$ 的值。

$p[]$ 数组求解

引入两个变量,分别为idmx。其中id为一个已经检查过了的最大的回文字符串的中心点,mx为这个回文字符串的最终点。在马拉车算法的过程中,我们不断的对这两个变量进行更新。在这个过程中,我们有公式:
$$
p[i] = \min(mx - i, p[2\times id - i])
$$
现在我们就重点来讲解这个公式,如下图所示(其中 $j$ 是 $i$ 关于 $id$ 的对称点($j = 2\times id - i$),蓝色串➀为以 $j$ 为中心的回文串,橙色串为以 $i$ 为中心的回文串,绿色串为以 $id$ 为中心的回文串):

1565748502350

目前我们已经求得了满足 $0 \leq x \leq i - 1$ 的 $p[x]$,接下来就是要使用以前的数据推得 $p[i]$。会有如下情况

  1. $i \leq mx$

    由于 $j$ 与 $i$ 关于 $id$ 对称,所以以 $j$ 为中心的回文串关于 $id$ 对称一下就成了以 $i$ 为中心的回文串。所以我们这个时候需要判断一下情况:

    1. 如果橙色串的末尾没有超过 $mx$, 即 $p[j] \leq mx - i$,此时 $p[i] = p[j]$。
    2. 如果橙色串的末尾超过了$mx$,即 $p[j] > mx - i$,此时就不能确定 $p[i] = p[j]$ 一定会成立了。则先赋值 $p[i] = mx - i$ ,然后手动向两边扩来得到最长回文子串。为什么 $p[j] = mx -i + 1$ 的情况归到了这里?因为当 $p[j] = mx -i + 1$,我们的回文子串直接定到了 $mx$ 上,我们不能确定 $mx$ 以后的位是否还能满足关于 $i$ 回文。
  2. $i > mx$

    那我们只能保证 $mx - i $ 这一段是满足的,所以我们就先让 $p[i] = mx -i$,其余部分使用笨方法慢慢扩张。

有没有可能橙色串的左端超过了 $mx$ 的对称点呢?不可能。如果说左端超过了 $mx$ 的对称点,且中心位于 $i$ 的话,则 $i$ 为中心的回文字串长度会超过以 $id$ 为中心的回文字串,也就是说以 $j$ 为中心的回文子串长度超过了 $id$ 为中心的回文字串,那么我的 $id$ 在之前应该被更新为 $j$。所以这种情况是不存在的。

算法模板

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
string Manacher(string str)
{
/*改造字符串*/
string res="$#";
for(int i=0; i < (int)str.length(); ++i) {
res += str[i];
res += "#";
}

/*数组*/
vector<int> p(res.length(), 0);
int mi = 0, right = 0; //mi为最大回文串对应的中心点,right为该回文串能达到的最右端的值
int maxLen = 0, maxPoint = 0; //maxLen为最大回文串的长度,maxPoint为记录中心点

for (int i = 1; i < res.length(); ++i){
p[i] = (right > i)? min(p[2 * mi - i], right - i) : 1; //关键句,文中对这句以详细讲解

while(res[i + p[i]] == res[i - p[i]])
++p[i];

if(right < i + p[i]) //超过之前的最右端,则改变中心点和对应的最右端
{
right = i + p[i];
mi = i;
}

if(maxLen < p[i]) //更新最大回文串的长度,并记下此时的点
{
maxLen = p[i];
maxPoint = i;
}
}
return str.substr((maxPoint - maxLen) / 2, maxLen - 1);
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×