最大回文子串-Manacher线性算法实现

发表于 更新于 Artalk： loading...
最大回文子串 中心拓展 manacher

个人认为，Manacher算法和Kmp有异曲同工之妙

之前转载过一篇关于Manacher算法的乐扣题解。初次学习，不甚理解，最近复习了Kmp算法后，豁然开朗

题目描述

LeetCode 5. 最长回文子串

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

子串：不可以删减个别字符，区别于「子序列」，连续子序列

回文串：正向和反向输出一致的字符串。例如：“明天到操场操到天明”

示例

1
2
input: s = "abac"
output: "aba"

暴力做法

最直观的做法，枚举每个子串，然后判断各自是否为回文串

1
2
3
4
5
6
7
8
9
10
11
for (int i = 1; i < n; ++i) {
    for (int j = i; j >= 0; --j) {
        if (isPalind(s, j, i)) {
            if (res < end - start) {
                start = j;
                end = i + 1;
            }            
        }
    }
}
return s.substring(start, end);

枚举每个子串的时间复杂度是 O(n2)\Omicron(n^2) ，而判断是否为回文串的操作是 O(n)\Omicron(n) 的

整体下来的时间复杂度为 O(n3)\Omicron(n^3) ，显然不够理想

中心拓展

由于回文串是「中心对称」的，判断回文串一般也是利用两个指针，从两边向中间扫描，进行比较

降低时间复杂度，我们可以减少指针扫描的躺数，将枚举子串和判断回文串结合起来

具体做法是，最外层循环，将每次枚举的点作为回文中心，然后用两个指针l和r向外拓展，如果 s[l] != s[r] ，即可终止扫描。不是回文串的子串是没有必要枚举的。

这就是中心拓展，时间复杂度降低到 O(n2)\Omicron(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for (int i = 0; i < n; ++i) {
    int cur = Math.max(maxP(s, i, i), maxP(s, i, i + 1));
    if (cur > end - start + 1) {
        start = i - (cur - 1) / 2;
        end = i + cur / 2;
    }
}

// ...
// 最长回文串的长度
public int maxP(String s, int l, int r) {
    int n = s.length();
    while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
        l--;
        r++;
    }
    return r - l - 1;
}

Manacher算法

优化中心拓展

中心拓展算法之所以是 O(n2)\Omicron(n^2) 的，是因为每次枚举了回文中心，然后都是从0开始，向外拓展，进行判断

Manacher算法是在中心拓展的基础上进行了优化，针对每个回文中心，会利用已有的信息，生成一个初始拓展距离，并不会从零开始

重点在于，何为『已有的信息？』，下面举例说明

令 f[i]f[i] 表示中心为 s[i]s[i] 时，可以拓展出的最大回文半径

核心是利用了「回文串的对称性」

例如，一个字符串s="01210601210"是个回文串，"01210"和"012’10"关于‘6’对称，当扫描到2’时，由于已知s是回文串，那么2’关于2对称，2’两侧的字符串也同样地和2两侧的字符串对称，那么

「2’目前可以拓展的距离必定和2相同」

manacher.drawio-2

由于以2为中心的最大回文半径f[2]已经记录下来，因此f{2’}可以直接初始化为f[2]，而不必从零开始拓展

算法流程

变量定义

利用数组 f[]f[] 保存每个中心的最大回文半径

在枚举每个回文中心的迭代中，维持两个变量:

  1. iMax。子串 s[0→i]s[0\to i] 中，有着最大回文半径的回文中心点
  2. rMax。 s[0→i]s[0 \to i] 中，以iMax为中心的最大回文子串的右端点，数值上等于 iMax+f[iMax]−1\text{iMax} + f[\text{iMax}] - 1

具体流程

迭代枚举回文中心 ii ：

  1. 初始化 f[i]f[i]，记 j=2×iMax−ij=2\times iMax - i 是点 ii 关于 iMaxiMax 对称的点
    1. 如果 i<rMaxi < rMax ，即点 ii 在「当前具有最大回文半径」的点 iMaxiMax 的势力范围内，就可以利用左侧对称点 jj 的信息 f[j]f[j] 来初始化 f[i]f[i] ，唯一需要注意的是，「初始的」拓展距离不能超出 iMaxiMax 的势力范围。f[i]=min{f[j],rMax−i+1}f[i] = min\{f[j], rMax-i + 1\}
    2. 如果 i>rMaxi > rMax ，说明点 ii 已经超出了以 iMaxiMax 为中心、当前最大回文子串的范围，无法利用已有的 f[]f[] 信息，直接初始化为1。f[i]=1f[i]=1
  2. 在初始化的基础上，开始向两边拓展

在迭代中，如果以当前 ii 点为中心拓展出的最大半径大于当前的 rMax−iMax+1rMax-iMax + 1 ，则更新 iMaxiMax 和 rMaxrMax

算法分析

Kmp算法，利用了next数组，在失配时，主串不用后退，而是利用已知的「相等前后缀」信息，移动副串即可

Manacher算法类似，利用回文串的对称性，利用已知的对称点的最大半径信息，来初始化该点的 f[i]f[i] 。在整个过程中，rMaxrMax 只会不断向右移动，不会减小，因此将整体时间复杂度优化到 O(n)\Omicron(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
public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) {
        return "";
    }
    int rm = 0, im = 0, n = s.length();
    StringBuilder sb = new StringBuilder();
    sb.append("$#");
    for (int i = 0; i < n; ++i) {
        char ch = s.charAt(i);
        sb.append(ch); sb.append('#');
    }
    sb.append('!');
    char[] chs = sb.toString().toCharArray();
    int m = chs.length;
    int[] f = new int[m - 1];
    int start = 0, end = 0;
    // 马拉车基于中心拓展，但是每次拓展，都会用到已有的信息，
    // f[i] 表示以i为中心，可以向两边拓展出的「最大半径」
    // 每次中心拓展维持两个变量: 1.'im':当前最大回文子序列的中心
    // 2.'rm':当前最大回文子序列的右端点 (f[im]=rm-im+1) 
    for (int i = 1; i < m - 1; ++i) {
        // 中心拓展前，进行初始化
        // 情况1: 当前i < rm， 2 * im - 1是i关于im的对称点，由于对称性（s[2*im-1~im] 和s[im~i]）
        // f[i]可以使用已有的f[2*im-1]信息来初始化，f[i]=f[2*im-1]，再加上个 rm-i+1 的限制
        // 情况2: i > rm，直接初始化为1
        f[i] = (i <= rm) ? Math.min(rm - i + 1, f[2 * im - i]) : 1;
        // 中心拓展
        while (chs[i + f[i]] == chs[i - f[i]]) ++f[i];
        // 如果以i为中心可拓展出的最大半径大于rm-im+1，更新
        if (f[i] > rm - im + 1) {
            im = i; rm = i + f[i] - 1;
            start = i - f[i] + 1;
            end =  i + f[i] - 1;   
        }
    }
    StringBuilder res = new StringBuilder();
    for (int i = start; i <= end; ++i) {
        if (chs[i] == '#') continue;
        res.append(chs[i]);
    }
    return res.toString();
    
}

📔博文图谱

提及本博文的链接