Manacher算法

Manacher算法是一种用于在字符串中查找最长回文子串的算法。它通过将字符串转换为一个新的字符串，并利用回文的对称性来加速查找过程。也是一种动态规划算法。

时间复杂度

O(n)O(n)

空间复杂度

O(n)O(n)

算法步骤

1. 预处理

当回文串的长度为奇数时，回文串的中心是唯一的，不会出现重复，因此要保证回文串的长度为奇数。一奇一偶相加，结果为奇数。

为此，在开头插入一个不存在于原字符串中的特殊字符（通常是^），在结尾插入一个不存在于原字符串中的特殊字符（通常是$），在原字符串的每个字符之间插入一个不存在于原字符串中的特殊字符（通常是#），这样回文串的长度就变成了奇数。

1
2
3
4
5
6
def manacher(s):
    # 预处理字符串
    T = '^#' + '#'.join(s) + '#$'
    n = len(T)
    P = [0] * n   # 回文半径数组
    C, R = 0, 0   # 回文中心和回文右边界

2. 计算回文半径

在计算回文半径时，需要考虑回文的对称性。对于回文串，如果以某个字符为中心，那么以该字符为中心的回文串的半径就是该字符到回文串两端的距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def manacher(s):
    # 预处理字符串
    T = '^#' + '#'.join(s) + '#$'
    n = len(T)
    P = [0] * n   # 回文半径数组
    C, R = 0, 0   # 回文中心和回文右边界
    # 计算回文半径
    for i in range(1, n - 1):
        i_mirror = 2 * C - i   # 计算i关于C的对称点
        if R > i:
            # 如果i在回文右边界R的左侧，则i的回文半径至少为i到R的距离
            P[i] = min(R - i, P[i_mirror])
        else:
            # 如果i在回文右边界R的右侧，则i的回文半径至少为0
            P[i] = 0
        # 尝试扩展回文串
        while T[i + P[i] + 1] == T[i - P[i] - 1]:
            P[i] += 1
        # 更新回文中心和回文右边界，如果i的回文半径大于R，则更新回文中心和回文右边界，保证回文中心和回文右边界是当前最大的
        if i + P[i] > R:
            C = i
            R = i + P[i]

3. 找出最长回文子串

在计算回文半径时，记录回文中心和回文右边界，最后遍历回文半径数组，找出最大的回文半径，即为最长回文子串的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
def manacher(s):
    # 预处理字符串
    # 略
    # 计算回文半径
    # 略
    # 找出最长回文子串
    max_len = 0
    max_center = 0
    for i in range(1, n - 1):
        if P[i] > max_len:
            max_len = P[i]
            max_center = i
    return T[max_center - max_len:max_center + max_len + 1].replace('#', '')

例题1:最长回文子串

(Leetcode)5.最长回文子串

题目描述：

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

示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

解题思路：

直接使用Manacher算法计算出各个字符为中心的最长回文子串，然后找出最长的回文子串。

代码实现：

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
class Solution {
public:
    string longestPalindrome(string s) {
        // 马拉车算法
        // 预处理
        string str = "$#";
        for(char& c : s) {
            str = str + c;
            str = str + '#';
        }
        int n = str.size();
        vector<int> p(n, 0);
        int c = 0;     // 初始化中心
        int right = 0; // 初始化最右边界
        for(int i=1; i<n; i++) {
            if(i < right) {
                // 利用和i点关于中心c点对称的点的回文半径快速求出i点的回文半径
                // 同时注意回文半径最多不会超过右边界
                p[i] = min(p[2*c-i], right-i);
            } else {
                p[i] = 1; // 至少包括自己，回文半径为1
            }
            // 向点i两端扩展
            while(i-p[i]>=0 && i+p[i]<n && str[i-p[i]] == str[i+p[i]]) {
                p[i]++;
            }
            // 更新中心节点和右边界
            if(i+p[i] > right) {
                // 当前节点的回文半径已经超过了右边界
                // 保证当前的右边界永远是当前最大的
                c = i;
                right = c + p[c];
            }
        }
        // 从p数组中找到最达到回文半径和中心
        int maxLen = 0;
        int center = 0;
        for(int i=1; i<n; i++) {
            if(p[i]-1 > maxLen) {
                // 如果左右回文半径大于当前值，更新
                maxLen = p[i]-1;
                center = i;
            }
        }
        // 提取子串
        // 映射回原字符串
        int start = (center - maxLen)/2;
        return s.substr(start, maxLen);
    }
};

例题2:分割回文串

(Leetcode)131.分割回文串

题目描述：

给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]

示例 2：

输入：s = “a”
输出：[[“a”]]

提示：

1 <= s.length <= 16
s 仅由小写英文字母组成

解题思路：

先使用Manacher算法计算出以每个字符为中心的最长回文子串，然后使用回溯算法找出所有可能的分割方案，在判断切分出来的子串是否是回文串的时候可以使用Manacher算法计算出的回文半径p[i]减少时间复杂度。

代码实现：

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
67
68
69
70
class Solution {
private:
    vector<string> path;
    vector<vector<string>> ans;
    vector<int> p;
public:
    void mancher(string s) {
        string t = "$#";
        for(char& c : s) {
            t += c;
            t += '#';
        }
        int n = t.size();
        p.resize(n, 0);
        int c = 0;
        int r = 0;
        for(int i=1; i<n; i++) {
            if(i<r) {
                p[i] = min(p[2*c-i], r-i);
            } else {
                p[i] = 1;
            }
            // 扩展左右边界
            while(i-p[i]>=0 && i+p[i] <n && t[i-p[i]] == t[i+p[i]]) {
                p[i]++;
            }
            // 更新右边界
            if(i+p[i] > r) {
                c = i;
                r = i+p[i];
            }
        }
    }

    // 判断当前子串是不是回文子串
    bool isPalindrome(string& s, int left, int right) {
        // 左闭右闭
        int center = left+right+2;  // 映射到预处理字符串的中心
        int len = right - left + 1; // 子串长度
        return p[center] >= len+1;  // 只有当前中心点的回文半径大于等于当前子串的长度，才能算回文子串
    }

    void backtracking(string s, int begin) {
        int n = s.size();
        if(begin == n) {
            ans.push_back(path);
            return;
        }
        for(int i=begin; i<n; i++) {
            // 裁剪的子串一定是从当前开头开始的
            if(isPalindrome(s, begin, i)) {
                // 当前子串是回文串，尝试裁剪
                path.push_back(s.substr(begin, i-begin+1));
                backtracking(s, i+1);
                path.pop_back();
            }
        }
        return;
    }
    vector<vector<string>> partition(string s) {
        // 清理
        path.clear();
        ans.clear();
        // 预处理字符串信息
        mancher(s);        
        // 回溯算法找出所有切分方案
        backtracking(s, 0);
        return ans;
    }
};