「转载」Manacher算法-查找最大回文子串的线性方法

发表于 更新于 Artalk： loading...

前言

转载自剑指 Offer II 020. 回文子字符串的个数的官方题解

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/a7VOhD/solution/hui-wen-zi-zi-fu-chuan-de-ge-shu-by-leet-ejfv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

剑指 Offer II 020. 回文子字符串的个数

问题描述：

给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例：

1
2
3
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

方法一：中心拓展

思路与算法

计算有多少个回文子串的最朴素方法就是枚举出所有的回文子串，而枚举出所有的回文字串又有两种思路，分别是：

  • 枚举出所有的子串，然后再判断这些子串是否是回文；
  • 枚举每一个可能的回文中心，然后用两个指针分别向左右两边拓展，当两个指针指向的元素相同的时候就拓展，否则停止拓展。

假设字符串的长度为 nn。我们可以看出前者会用 O(n2)O(n^2) 的时间枚举出所有的子串 s[li…ri]s[l_i…r_i]，然后再用 O(ri−li+1)O(r_i−l_i+1) 的时间检测当前的子串是否是回文，整个算法的时间复杂度是 O(n3)O(n^3)。

而后者枚举回文中心的是O(n)O(n)，对于每个回文中心拓展的次数也是 O(n)O(n) 的，所以时间复杂度是 O(n2)O(n^2)。所以我们选择第二种方法来枚举所有的回文子串。

在实现的时候，我们需要处理一个问题，即：如何有序地枚举所有可能的回文中心，我们需要考虑回文长度是奇数和回文长度是偶数的两种情况。如果回文长度是奇数，那么回文中心是一个字符；如果回文长度是偶数，那么中心是两个字符。当然你可以做两次循环来分别枚举奇数长度和偶数长度的回文，但是我们也可以用一个循环搞定。我们不妨写一组出来观察观察，假设 n=4n=4，我们可以把可能的回文中心列出来：

编号 ii回文中心左起始位置lil_i回文中心右起始位置 rir_i
000
101
211
312
422
523
633

由此我们可以看出长度为nn的字符串会生成 2n−12n−1 组回文中心 [li,ri][l_i, r_i]，其中li=⌊i2⌋l_i = \lfloor \frac{i}{2}\rfloor，ri=li+(i mod 2)r_i = l_i + (i \bmod 2)。这样我们只要从 00 到2n−22n−2 遍历 ii，就可以得到所有可能的回文中心，这样就把奇数长度和偶数长度两种情况统一起来了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size(), ans = 0;
        for (int i = 0; i < 2 * n - 1; ++i) {
            int l = i / 2, r = i / 2 + i % 2;
            while (l >= 0 && r < n && s[l] == s[r]) {
                --l;
                ++r;
                ++ans;
            }
        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度：O(n2)O(n^2)。

  • 空间复杂度：O(1)O(1)。

方法二：Manacher 算法

思路与算法

Manacher 算法是在线性时间内求解最长回文子串的算法。在本题中，我们要求解回文串的个数，为什么也能使用 Manacher 算法呢？这里我们就需要理解一下 Manacher 的基本原理。

Manacher 算法也会面临「方法一」中的奇数长度和偶数长度的问题，它的处理方式是在所有的相邻字符中间插入 ##，比如abaaabaa 会被处理成 #a#b#a#a##a#b#a#a#，这样可以保证所有找到的回文串都是奇数长度的，以任意一个字符为回文中心，既可以包含原来的奇数长度的情况，也可以包含原来偶数长度的情况。假设原字符串为 SS，经过这个处理之后的字符串为 ss。

我们用 f(i)f(i) 来表示以 ss 的第 ii 位为回文中心，可以拓展出的最大回文半径，那么 f(i)−1f(i)−1就是以 ii 为中心的最大回文串长度 （想一想为什么）。

Manacher 算法依旧需要枚举 ss 的每一个位置并先假设它是回文中心，但是它会利用已经计算出来的状态来更新 f(i)f(i)，而不是向「中心拓展」一样盲目地拓展。具体地说，假设我们已经计算好了[1,i−1][1,i−1]区间内所有点的 ff（即我们知道 [1,i−1][1,i−1]这些点作为回文中心时候的最大半径）， 那么我们也就知道了 [1,i−1][1,i−1] 拓展出的回文达到最大半径时的回文右端点。例如 i=4i=4 的时候 f(i)=5f(i)=5，说明以第 44个元素为回文中心，最大能拓展到的回文半径是 55，此时右端点为 4+5−1=84+5−1=8。所以当我们知道一个 ii对应的 f(i)f(i) 的时候，我们就可以很容易得到它的右端点为 i+f(i)−1i+f(i)−1。

Manacher 算法如何通过已经计算出的状态来更新 f(i)f(i)呢？Manacher 算法要求我们维护「当前最大的回文的右端点 rmr_m」以及这个回文右端点对应的回文中心 imi_m。我们需要顺序遍历 ss，假设当前遍历的下标为 ii。我们知道在求解 f(i)f(i) 之前我们应当已经得到了从[1,i−1][1,i−1]所有的 ff，并且当前已经有了一个最大回文右端点 rmr_m以及它对应的回文中心imi_m。

  • 初始化 f(i)f(i)

    • 如果 i≤rmi≤r_m，说明 ii 被包含在当前最大回文子串内，假设 jj 是 ii 关于这个最大回文的回文中心 imi_m的对称位置（即 j+i=2×imj+i=2 \times i_m），我们可以得到f(i)f(i) 至少等于min{f(j),rm−i+1}min\{f(j),r_m−i+1\}，也即min{f(2×im−i),rm−i+1}min\{f(2 \times i_m - i), r_m -i +1\}。这里将 f(j)f(j)和 rm−i+1r_m−i+1 取小，是先要保证这个回文串在当前最大回文串内。（思考：为什么 f(j)f(j)有可能大于 rm−i+1r_m−i+1?）

    • 如果 i>rmi>r_m，那就先初始化 f(i)=1f(i)=1。

  • 中心拓展

    • 做完初始化之后，我们可以保证此时的 s[i+f(i)−1]=s[i−f(i)+1]s[i+f(i)−1]=s[i−f(i)+1]，要继续拓展这个区间，我们就要继续判断 s[i+f(i)]s[i+f(i)]和 s[i−f(i)]s[i−f(i)] 是否相等，如果相等将 f(i)f(i)自增；这样循环直到 s[i+f(i)]≠s[i−f(i)]s[i+f(i)]≠s[i−f(i)]，以此类推。

      我们可以看出循环每次结束时都能保证 s[i+f(i)−1]=s[i−f(i)+1]s[i+f(i)−1]=s[i−f(i)+1]，而循环继续（即可拓展的条件）一定是 s[i+f(i)]=s[i−f(i)]s[i+f(i)]=s[i−f(i)]。

      这个时候我们需要注意的是不能让下标越界，有一个很简单的办法，就是在开头加一个 $$，并在结尾加一个 !!，这样开头和结尾的两个字符一定不相等，循环就可以在这里终止。

这样我们可以得到 ss 所有点为中心的最大回文半径，也就能够得到 SS 中所有可能的回文中心的的最大回文半径，把它们累加就可以得到答案。

代码

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
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        string t = "$#";
        for (const char &c: s) {
            t += c;
            t += '#';
        }
        n = t.size();
        t += '!';

        auto f = vector <int> (n);
        int iMax = 0, rMax = 0, ans = 0;
        for (int i = 1; i < n; ++i) {
            // 初始化 f[i]
            f[i] = (i <= rMax) ? min(rMax - i + 1, f[2 * iMax - i]) : 1;
            // 中心拓展
            while (t[i + f[i]] == t[i - f[i]]) ++f[i];
            // 动态维护 iMax 和 rMax
            if (i + f[i] - 1 > rMax) {
                iMax = i;
                rMax = i + f[i] - 1;
            }
            // 统计答案, 当前贡献为 (f[i] - 1) / 2 上取整
            ans += (f[i] / 2);
        }
    
        return ans;
    }
};

复杂度分析

  • 时间复杂度：O(n)O(n)。即 Manacher 算法的时间复杂度，由于最大回文右端点 rmr_m只会增加而不会减少，故中心拓展进行的次数最多为O(n)O(n)，此外我们只会遍历字符串一次，故总复杂度为O(n)O(n)。

  • 空间复杂度：O(n)O(n)。