Manacher 算法学习笔记

Ciel Yang 收录于类别学习算法

2020-03-13 2020-03-13 约 1671 字预计阅读 4 分钟

Manacher 算法的针对问题是找出字符串的最长回文子串，或者最长回文子串的长度。本文是个人对 Manacher 算法关键点的总结，以备复习，会省略容易理解的内容，只记录个人不熟悉的知识点。

基本思路

核心：利用动态规划的方法，把每中状态的处理次数降低为常数次，这样遍历 n 种状态的实际复杂度就是 O(n)。

中心扩展法

首先，Manacher 算法脱胎于中心扩展法，即：

从左向右遍历字符串所有字符
把每个字符当作回文字符串的对称中心或者左半边的末尾
不断扩展回文字符串，保证它满足对称性质
一旦扩展结束（两端不等或到达字符串尽头），就得到一个回文子串

可以看出，中心扩展法有两个不尽如人意的地方：

不确定字符是回文子串的对称中心还是左半边末尾，即不确定回文子串长度是偶数还是奇数
每个回文子串都要遍历所有字符

优化设计

第一个问题好处理，只需要在原字符串的每个字符之间添加同样的分隔符，并在开头和末尾添加分隔符即可——这样就能够把所有回文子串转化为奇数长度的回文子串。第二个问题则比较难处理，尤其是如果采用了上述添加辅助分隔符的方法后，字符串长度增加，遍历次数会飞速增加，毕竟中心扩展法有很多重复操作（时间复杂度是 O(n^2)）。

首先，假设我们已经得到了以每个字符为对称中心的回文子串的长度，即数组 p。那么，对任意一个回文字子串 s，不妨记它的中心坐标为 mid，它的右侧子串内的任意一个字符坐标记为 i。显然，坐标 i 关于 mid 对称的坐标为 $2 \times mid - i$，那么在 s 以内以 s[i] 为中心对称的回文子串必定在左边有关于 mid 完全对称的子串，那么 p[i] 最小值是 $min{(p[2 \times mid - i],\ p[mid] - i)}$。至于，为什么是最小值，而非确定值也很容易理解，毕竟 s[i] 为中心的回文子串完全有可能比 s 更长。这样，我们就利用回文字符串的对称性质找到了一个递推关系，至少可以帮助我们确定新状态的下界，可以省略很多重复检查操作。然后，再从这个下界开始就可以使用基本的暴力方法确定 p[i] 的实际值。

其次，为了进一步完善上述想法，还要考虑如何找到 mid 的值，要注意到 mid 是回文子串的中心，而且在 i 的左边，p[mid] 也就一定已经被我们处理过了。那么，实际上我们只要考虑 p[i] 确定后如何更新 mid 的值以匹配下标大于 i 的字符即可，根据递推关系就能不断求出所有可能的 mid 取值。不难发现，确定了 p[i] 之后我们得到了一个新的回文子串和它的对称中心，那么是否要把 mid 更新为 i 呢？答案是不一定，有可能 i 对应的回文子串非常短，这样下标大于 i 的字符仍然使用原有 mid 的值即可。也就是说，只有 p[i] + i > p[mid] + mid 的时候，mid 才有必要更新为 i，以确保更多的右侧字符能够找到对应的 mid 值，这样就能去除更多的重复处理操作。

注意：只要发生 index > p[mid] + mid 的情况，那么 p[index] 的值就一定不能利用递推关系节省操作，仍然要使用基本的暴力检查方法。

伪码构建

实际的预处理操作更复杂一点点，即在原先设计的辅助字符数组开头和结尾再加上一对不等的字符，把下标越界转化为字符不相等
实际必须记录每个可能的 mid 值，而且为了方便计算，不妨也记录一个 right 值为 mid + arr[mid]
记录辅助字符数组中回文子串的“对称半径”更方便递推运算，即对称中心到边界的距离
“对称半径”减去 1 就是原字符串中对应的回文子串的长度
辅助字符数组中的字符下标除以 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
fun longestPalindrome(s: String): String {
    // 预处理
    arr = CharArray(2 * s.length + 3)
    arr[0] = '^'
    arr[1] = '#'
    cnt = 2
    for (c in s) {
        arr[cnt++] = c
        arr[cnt++] = '#'
    }
    arr[cnt++] = '$'
    p = IntArray(cnt)

    // 递推操作
    right = 0
    mid = 0
    maxMid = 0
    for (i in 1 until cnt - 1) {
        if (i < right) p[i] = min(p[2 * mid - i], right - i)
        else p[i] = 0
        while (arr[i - 1 - p[i]] == arr[i + 1 + p[i]]) p[i]++
        if (i + p[i] > right) {
            mid = i
            right = i + p[i]
        }
        if (p[maxMid] < p[i]) maxMid = i
    }

    start = (maxMid - p[maxMid]) / 2
    return s.substring(start, maxMid + p[maxMid])
}

实际代码

 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
fun longestPalindrome(s: String): String {
    // 初始化
    val arr = CharArray(s.length * 2 + 3)
    val delimiter = '#'
    arr[0] = '^'
    arr[1] = delimiter
    var cnt = 2
    for (c in s) {
        arr[cnt++] = c
        arr[cnt++] = delimiter
    }
    arr[cnt++] = '$'
    val lengths = IntArray(cnt)

    var right = 0       // 回文字符串的最右下标
    var mid = 0         // 回文字符串的中心
    var maxMid = 0      // 最长回文字符串的中心
    for (i in 1 until cnt - 1) {
        lengths[i] = if (i < right) min(lengths[2 * mid - i], right - i) else 0

        while (arr[i - 1 - lengths[i]] == arr[i + 1 + lengths[i]]) lengths[i]++

        if (right < i + lengths[i]) {
            mid = i
            right = i + lengths[i]
        }
        if (lengths[i] > lengths[maxMid]) maxMid = i
    }

    val start = (maxMid - lengths[maxMid]) / 2
    return s.substring(start, start + lengths[maxMid])
}

目录