Manacher算法

目录
– Manacher算法
– 问题背景
– 暴力解法
– 原理分析
– 代码实现
– 时间估计
– Manacher算法
– 原理分析
– 找到参考中心
– 找到镜像位置
– 分类讨论
– 情况一 完全在内部
– 情况二 超出
– 情况三 擦边
– 算法实现

问题背景

给出一个字符串, 有以下一些概念:
+ 子串: 从字符串中任意取出的一段连续的部分, 至少一个字符, 在这个问题中子串可以是原串自己
+ 回文字符串: 正着读和反着读都是一样的字符串, 如: “上海自来水来自海上”
+ 回文子串: 是回文字符串的子串
+ 回文半径/直径: 字面意思, 但要区别字符串长度奇偶不同的区别, 举例
+ “abcba” 的回文半径为3, 回文直径为5
+ “abba” 的回文半径为2, 回文直径为4

Manacher算法要解决的问题是:

给出一个字符串, 求出所有子串中的最长回文半径.

样例:

输入: “abcbaada”
输出: 3

暴力解法

原理分析

即枚举即可, 不过枚举也讲究方法
考虑到回文串的中心点可能在任意一个字符上, 也有可能在两个字符串之间
因此我们首先要在每个间隙中加入填充字符

以"abcbaada"为例, 通过一个函数(容易实现), 将原字符串改写成"#a#b#c#b#a#a#d#a#"这样的字符串

接着遍历字符串, 将每个字符作为中心尝试向两边扩展, 即每次比对左右两个字符是否相等, 直至不等或到达边界

有趣的一点: 填充字符串可以是任意的(即便会和原串中的字符重复)
细想, 无论以哪个字符为中心, 在向两侧扩大的时候, 检测的那两个字符一定是: 要么都来自原串, 要么都是填充字符
因此不会涉及到填充字符与原串字符的比较, 故填充字符对结果没有影响

代码实现

int getLongestPalindrome(const string& s) {
    if(s.empty()) return 0;
    string str = "#";
    for(auto ch : s) {
        str += ch;
        str += '#';
    }
    int longest = 1;
    for(int i = 0; i < str.size(); ++i) {
        int l = i - 1, r = i + 1;
        while(l >= 0 && r < str.size() && str[l] == str[r]) {
            --l;
            ++r;
        }
        longest = max(longest, r - l - 1);
    }
    return longest;
}

时间估计

该方法时间复杂度为O(n^2)
最简单的例子: "aaaaaaaaaaaaa..."

Manacher算法

原理分析

Manacher算法的核心思想是利用已知的回文子串的信息, 来推断新的回文子串.

好的算法都是这个共性, 用已知的信息去推断更多的信息
能不算就不算, 少算一次是一次

怎么利用已知信息?
考虑一个回文字符串"abalaba", 其特点是: 自身是回文串的情况下, 左右两翼也分别是回文串
既然是回文串, 那么可以将中间的"l"视为一面镜子, 也就是当我们在检验以右侧"b"为中心的回文子串时, 可以参考左侧"b"的回文子串的情况
当然, 如果原字符串是"abalabal", 那么对于第二个"b"而言, 其半径是3, 未必与第一个"b"的半径相同, 所以还要做其他的检查
但至少, 我们知道了第二个"b"的回文半径不小于第一个"b"的回文半径
换言之也就是说: 我们可以在不进行任何检查的情况下, 将第二个"b"的回文半径定为3, 并在此基础上检查

少算一点是一点, 偷懒成功!

核心机制搞清楚了, 我们接着分步骤来思考具体实现办法

找到参考中心

由于我们是通过遍历方式逐个判断的, 因此我们要找的参考中心所对应的那个回文字符串一定要包含着现在遍历到的位置
为了保证这一点, 我们可以考虑设计两个变量: “最远右边界”和其对应的”中心点”

注意这里我们定义右边界是字符串的最后一位的 “后一位”

举例:
对于加工后的字符串"#a#b#b#a#", 当遍历到2下标对应的'#'时, 其最大回文字符串是"#", 其最远右边界应当是3, 由于和先前的"#a#"所营造的右边界一致, 所以保留”中心点”仍为'a'对应的下标1

那么只要我们现在要判定的下标在”最远右边界”中, 就能知道对应的”中心点”

对于不在的情况, 自然没有优化, 还得老老实实算

找到镜像位置

我们记现在要确认的位置为i, “中心点”为c, 镜像位置为i'
显然, 满足中点公式: i + i' == 2 * c

接着我们根据i'的情况分类讨论

分类讨论

情况一 完全在内部

所谓 “完全” , 要求i'对应的字符串左侧在c对应的字符串左侧的右边, 不能是同一个边界

例如下图所示:

此时, i的回文半径必定和i'的一致

证明很简单, 只需要假设还能扩展, 用反证法即可证明

情况二 超出

超出就是i'左边界在c左边界左侧

例如下图所示:

这个例子中i'的最长回文子串的左侧是0位置的'j', 在L的左侧, 已经超出
在这种情况下, i的回文半径一定是i到R的这段长度

证明: c的边界之所以只能到达L 和 R, 说明再外侧的两位必定不一样(这里的1和15位)
而i'之所以能超出, 说明1和5一致
又因为对称性, 11和5等同
联立可得15和11不相同
因此, 不需要逐位检查就能确定i最多扩到R停手

情况三 擦边

称i'左边界和L重合为擦边
这时唯一能确定的是, 回文半径必定大于等于i到R这段的长度(由对称性所得)
造成不确定的根本原因是: R右侧的字符之前未检验过, 不属于已知信息
因此要从R右侧开始尝试扩展, 逐个字符检验

但是i到R这段不用算, 还是那句话, 能偷懒则偷懒

算法实现

#include <bits/stdc++.h>
using namespace std;

void process(string str, char *s, int len)
{
    int i = 0;
    while (i < 2 * len + 1)
    {
        s[i] = i & 1 ? str[i >> 1] : '#';
        i++;
    }
}

int Manacher(string str)
{
    int len = str.length();
    char s[len * 2 + 1];
    process(str, s, len);
    // cout << "s: ";
    // for (auto c : s)
    // {
    //     cout << c;
    // }
    // cout << endl;

    int radius[2 * len + 1];
    int lastCenter = -1;
    int rightBoarder = 0;
    int ans = 1;

    for (int i = 0; i < len * 2 + 1; i++)
    {
        if (i >= rightBoarder) // 无法优化的情况
        {
            int r = 1;
            while (i + r <= 2 * len && i - r >= 0 && s[i + r] == s[i - r])
                r++;
            radius[i] = r;
            lastCenter = i;
            rightBoarder = i + r;
        }
        else
        {
            int i2 = 2 * lastCenter - i;

            if (i + radius[i2] < lastCenter + radius[lastCenter]) // 情况一 完全在内部
            {
                radius[i] = radius[i2];
            }
            else if (i + radius[i2] > lastCenter + radius[lastCenter]) // 情况二 超出
            {
                radius[i] = lastCenter + radius[lastCenter] - i;
            }
            else // 情况三 擦边
            {
                int r = radius[i2];
                while (i + r <= 2 * len && i - r >= 0 && s[i + r] == s[i - r])
                    r++;
                radius[i] = r;
                lastCenter = i;
                rightBoarder = i + r;
            }
        }
        ans = max(ans, radius[i]);
    }

    return ans / 2;
}

int main()
{
    string s;
    cin >> s;
    cout << Manacher(s) << endl;
}

该代码纯手撸, 以可读性为主
更好的写法是:

先不考虑分类, 统一先定下不用验也能确定的半径
然后都往外扩, 因为如果确实直接是答案, 那么扩一次就失败了, 不影响复杂度
当然, 这里的不用验也能确定的半径需要细想一下
应当形如: R > i ? min(radius[i2],R-i) : 1