【数据结构与算法】Manacher算法

2023-03-14

边界 parr 回文

🌠作者：@阿亮joy.🎆专栏：《数据结构与算法要啸着学》🎇座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根目录👉前言👈👉Manacher算法👈👉最长回文子串👈👉总结👈👉前言👈如果给定一个字符串str，如何求解该字符串的最长

🌠作者：@阿亮joy.
🎆专栏：《数据结构与算法要啸着学》
🎇座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根

👉前言👈

如果给定一个字符串 str，如何求解该字符串的最长回文子串（注：子串必须是连续的，子序列不要求连续）。如字符 str 为 abc12320d1，其最长回文子串是 232，而不是回文子序列 12321。如果一个字符串是回文串，那么该字符串一定有个对称轴，使得左右两边的字符是对称的。比如：字符串 abcba 的对称轴是字符 c（实轴），字符串 abba 的对称轴是一条虚轴（不是关于某个字符对称）。

那么我们要求字符串的最长回文子串，我们很容易想到一种暴力的方法：遍历字符串的每一个字符，从该字符为中心向左右两边扩（左边和右边的字符相等就扩，不相等就停止），这样就能得到最长回文子串了。这种方法的时间复杂度是 O(N^2)，非常的暴力，而且这种方法不能够解决字符串长度为偶数的情况。如：字符串 122131221，因为回文串长度为偶数时，其对称轴是虚轴，这样就无法保证每个字符向左右两边扩都能得到以该字符为中心的最长回文串。

那如何保证能够得到偶数的回文串呢？这就需要学习本篇博客要介绍的 Manacher 算法。

👉Manacher 算法👈

Manachar 算法主要是处理字符串中关于回文串的问题的，它可以在 O(N) 的时间处理出以字符串中每一个字符为中心的回文串半径，由于将原字符串处理成两倍长度的新串，在每两个字符之间加入一个特定的特殊字符，因此原本长度为偶数的回文串就成了以中间特殊字符为中心的奇数长度的回文串了。

Manacher 算法提供了一种巧妙的办法，将长度为奇数的回文串和长度为偶数的回文串一起考虑。具体做法是：在原字符串的每个相邻两个字符中间插入一个分隔符，同时在首尾也要添加一个分隔符，分隔符可以是原串中的子串，但一般情况下都是使用 # 号作为分隔符。

如果 Manacher 算法也像上图的做法来求最长回文子串的话，那么它的时间复杂度也是 O(N^2)，那 Manacher 算法是如何将时间复杂度优化到 O(N) 的呢？我们一起来看一下！

Manacher 算法的优化就是通过已知信息来做到时间复杂度的优化。首先，我们需要知道回文半径和回文直径的概念。见下图所示：

知道回文半径和回文直径后，我们还需要知道一个概念—— 回文半径数组，就是我们将已经求得的回文半径放在数组中，那么该数组就被称为回文半径数组。还有最后两个概念，一个是回文右边界，另一个是回文中心。回文中心比较好理解，就是回文串的中心点下标。回文右边界是以每个字符为中心扩出来的回文串的右边界，它是一个整型。在扩的过程中，如果新生成的回文串的右边界比原来右边界还要右，这时候就需要更新回文右边界；否则不需要更新。如果回文右边界更新，回文中心就需要更新；而如果回文右边界没有更新，回文中心也不需要更新。

知道了上面的全部概念后，我们就来学习 Manacher 算法。Manacher 算法在更新回文数组的时候，会遇到两种情况：字符的下标超出回文右边界和字符的下标在回文右边界的范围内。

当字符的下标超出回文右边界时，我们就以该字符为中心向左右暴力两边扩，然后更新回文右边界。

当字符的下标在回文右边界的范围内，这时候就可以通过已用的信息（回文数组）来进行优化了。

字符下标在回文右边界内这种情况又可以根据 i’ 回文区域的不同分为三个小类：

第一小类：i’ 的整个回文区域都在 left 到 right 的范围内

第二小类：i’ 回文区域的左边界小于 left

第三小类：i’ 回文区域的左边界等于 left

Manacher 算法伪代码

// 返回值是回文半径数组
vector<int> Manacher(string& s)
{
// 1221 -> #1#2#1#2#1#
s 经过处理变成了 str

vector<int> pArr(str.size(), 0);// 回文半径数组
int right = -1;//回文右边界
int center = -1;// 回文中心

for(int i = 0; i < str.size(); ++i)
{
if(i在right的外部)
{
以i为中心，向左右两边暴力扩，回文右边界right变大
}
else
{
if(i'的回文区域在left到right范围内)
{
pArr[i] = pArr[2 * center - i]// 堆成性质
}
else if(i'回文区域的左边界小于left)
{
pArr[i] = right  + 1 - i;// 加一的原因是回文半径需要加上中心点i
}
else// i'回文区域的左边界等于left
{
从right范围之外的字符开始往外扩，然后确定回文半径pArr[i]
第一次扩失败了，回文右边界right不变
否则，回文右边界right变大
}
}
}

return pArr;
}
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

很显然，Manacher 算法的时间复杂度是 O(N)。

👉最长回文子串👈

根据 Manacher 算法的伪代码，我们可以改成以下的精简版本的代码

class Solution 
{
public:
    string longestPalindrome(string s) 
    {
        // babad --> #b#a#b#a#d
        // 加入分隔符#
        string tmp = "#";
        for(auto ch : s)
        {
            tmp += ch;
            tmp += "#";
        }

        vector<int> pArr(tmp.size(), 0);    // 回文半径数组
        int center = -1;   // 回文中心
        int right = -1;    // 回文右边界的再往右一个位置,最右的回文区域是R-1位置
        int start = 0;     // 最长回文子串的左边界
        int end = -1;      // 最长回文子串的右边界
        int Max = INT_MIN; // 最长回文子串的半径,即最长回文串的直径 / 2 + 1
        // 那么 Max - 1 就是原字符串的最长回文子串的长度
        
        // 每个位置都要求回文半径
        int size = tmp.size();
        for(int i = 0; i < size; ++i)
        {
            // i至少的回文区域,先更新给pArr[i]
            // 不需要扩就能知道i的最小回文区域
            // i在right外时,需要暴力扩,i的回文区域至少包括自己
            // i在right内,第一小类和第二小类是能够直接拿到的
            // 对于第一和第二小类,i的回文半径是(pArr[2 * center - 1]、right - i)中的较小值
            pArr[i] = right > i ? min(pArr[2 * center - i], right - i) : 1;
            // 第三小类是需要向左右两边扩才能确定的往,循环条件保证往外扩时不越界
            // 第一和第二小类第一次扩就会扩失败
            while(i + pArr[i] < size && i - pArr[i] > -1)
            {
                if(tmp[i + pArr[i]] == tmp[i - pArr[i]])
                    ++pArr[i];
                else
                    break;
            }

            // 更新回文右边界和回文中心
            if(i + pArr[i] > right)
            {
                right = i + pArr[i];
                center = i;
            }
            // 注：i+pArr[i]大于right并不意味着以i为中心的回文子串就是最长的回文子串
            // 而如果以i为中心的回文子串就是最长的子串,那么i+pArr[i]一定大于right

            // 更新最长回文子串的半径、左边界和右边界
            if(pArr[i] > Max)
            {
                Max = pArr[i];
                // 因为right是回文右边界的下一个位置,且最长回文子串
                // 的左边界加右边界等于两倍的center,所以可以推出
                // start + right - 1 = 2 * center
                start = 2 * center + 1 - right;
                end = right - 1;
            }
        }

        // 将最长回文子串还原出来
        // Max - 1 和 (end + 1 - start) / 2都是最长回文子串的长度
        string ret;
        for(int i = start; i <= end; ++i)
        {
            if(tmp[i] != '#')
                ret += tmp[i];
        }
        return ret;
    }
};
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
71
72
73
74