算法之Manacher算法

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2.7k 阅读时长 ≈ 5 分钟

算法之Manacher

给定一个字符串 s，找到 s 中最长的回文子串？

回文是一个正读和反读都相同的字符串，例如，“aba” 是回文，而 “abc” 不是。由于回文分为偶回文（比如 bccb）和奇回文（比如 bcacb），而在处理奇偶问题上会比较繁琐，所以这里我们使用一个技巧，具体做法是：在字符串首尾，及各字符间各插入一个字符（前提这个字符未出现在串里）。举个例子：s=“abbahopxpo”，转换为s_new=“#a#b#b#a#h#o#p#x#p#o#”

定义一个辅助数组int p[]，其中p[i]表示以 i 为中心的最长回文的半径，例如：

i0123456789101112131415161718
s[i]#a#b#b#a#h#o#p#x#p#
p[i]1212521212121214121

可以看出，p[i] - 1正好是原字符串中最长回文串的长度。p[i]-1的最大值就是我们的最终结果。

接下来可以得到如下结论:

  1. 设置两个变量，mx 和 id 。mx 代表以 id 为中心的最长回文的右边界，也就是mx = id + p[id]。
  2. 如果mx > i，那么P[i] >= MIN(P[2 * id - i], mx - i)。
  3. 对于 mx <= i 的情况，无法对 P[i]做更多的假设，只能P[i] = 1，然后再去匹配了。

对于第二点的分析如下:

当 mx - i > P[i] 的时候（j=2*id-i），以S[i]为中心的回文子串包含在以S[id]为中心的回文子串中，由于 i 和 j 对称，以S[j]为中心的回文子串必然包含在以S[id]为中心的回文子串中，所以必有 P[i] = P[j]，如下。

i0123456789101112131415161718
s[i]#a#b#b#a#h#o#p#x#p#
p[i]1212521212121214121
idmx
ji

当 P[i] >= mx - i 的时候，以S[i]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中，但是基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以S[i]为中心的回文子串，其向右至少会扩张到mx的位置，也就是说 P[i] >= mx - i。至于mx之后的部分是否对称，就只能老老实实去匹配了。

i0123456789101112131415161718
s[i]#a#b#b#a#h#o#p#x#p#
p[i]1212521212121214121
idmx
ji

对于 mx <= i 的情况，无法对 P[i]做更多的假设，只能P[i] = 1，然后再去匹配了。

对于manacher 算法:

  • 时间复杂度为 O(n)O(n)
  • 空间复杂度为 O(n)O(n)
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
public class Manacher {
    public String longestPalindrome(String s) {
        String newStr = preProcess(s);
        // rad[i]表示以i为中心的回文的最大半径，i至少为1，即该字符本身
        int [] rad = new int[newStr.length()];
        // right表示已知的回文中，最右的边界的坐标
        int right = -1;
        // id表示已知的回文中，拥有最右边界的回文的中点坐标
        int id = -1;
        // 2.计算所有的rad
        // 这个算法是O(n)的，因为right只会随着里层while的迭代而增长，不会减少。
        for (int i = 0; i < newStr.length(); i ++) {
            int r = 1;
            if (i <= right) {
                // 2.1.确定一个最小的半径, 新的点落在已有回文中，
                r = Math.min(rad[id] - (i - id), rad[2 * id - i]);
            }
            // 2.2.尝试更大的半径
            while (i - r >= 0 && i + r < newStr.length() && newStr.charAt(i - r) == newStr.charAt(i + r)) {
                r++;
            }
            // 2.3.更新边界和回文中心坐标
            if (i + r - 1> right) { // i的边界 在边界外
                right = i + r - 1;
                id = i;
            }
            rad[i] = r;
        }
        // 3.扫描一遍rad数组，找出最大的半径
        int maxLength = 0;
        int maxValuePos = 0;
        int Pos = 0;
        for (int r : rad) {
            if (r > maxLength) {
                maxLength = r;
                maxValuePos = Pos;
            }
            Pos++;
        }
        int realLen =  maxLength - 1;
        String huiwen;
        StringBuffer realHuiwen = new StringBuffer();
        if (realLen == 1) {
            return newStr.substring(maxValuePos,maxValuePos+1);
        } else {
            huiwen = newStr.substring((maxValuePos + 1 - rad[maxValuePos]), maxValuePos + rad[maxValuePos]);
            //去掉辅助字符
            for (int j = 0; j < huiwen.length(); j++) {
                if (j % 2 != 0)
                    realHuiwen = realHuiwen.append(huiwen.charAt(j));
            }
            return realHuiwen.toString();
        }
    }

    // 为了避免奇数回文和偶数回文的不同处理问题，在原字符串中插入'#'，将所有回文变成奇数回文
    public String preProcess(String str) {
        StringBuilder newStr = new StringBuilder();
        newStr.append('#');
        for (int i = 0; i < str.length(); i ++) {
            newStr.append(str.charAt(i));
            newStr.append('#');
        }
        return newStr.toString();
    }
}