fccc
搜索文章Ctrl+K

Appearance

Manacher算法

Manacher算法 ​

Manacher算法可以求解字符串s的最长回文子串长度，可以帮助理解回文半径数组
理解了manacher算法，再理解kmp算法会比较容易

回文串： 回文串就是一个对称的字符串，从左右两边开始读都相同。
奇数长度的回文串以中心字符为轴对称，如abcba以c为轴左右对称
偶数长度轴在字符串中心的虚轴，如adeeda虚轴在两个e之间

一、引入：暴力方法如何寻找最长回文串 ​

1.暴力方法 ​

暴力方法就是以每个字符为中心，往两边扩，扩的最长的那个就是最长回文长度

以xabacabay为例，以x向两边扩长度为1，以a向两边扩为1，以b向两边扩为3（aba）,以c向两边扩长度为7（abacaba）这个最长的就是

2.扩展串 ​

问题： 我们只能找到奇数长度的回文串，这样找的话偶数长度的回文串会错过，偶数长度是以虚轴为中心向两边扩，于是延伸出一个扩展串的概念

那么什么是扩展串呢?
我们在每两个字符中间插入一个#，比如abaaba，每个字符两边都有一个扩展字符变成#a#b#a#a#b#a#，能够统一奇偶回文，这样奇偶长度的就都能够找到了，只是长度会比较长，然后在计算出原始长度，扩展字符可以任意

3.Manacher回文半径 ​

回文半径： 简单来说就是，从中心出发走一半的位置，例如#a#b#a#,从b走到边界长度就是4，包含中心点。例如 #a#b#a#a#b#a# 对应的回文半径数组p就是[1, 2, 1, 4, 1, 2, 7, 2, 1, 4, 1, 2, 1]

回文半径和真实长度的对应： 真实长度=回文半径数组p[i]−1扩展回文串结尾下标和真实回文串终止位置的对应： 真实回文串终止位置 = 扩展回文串结尾下标 / 2
每个回文串的起点位置： start=(idx-p[idx])/2
真实回文串起始位置： 最长回文半径长度mx，mx的回文半径数组对应的下标pos，回文串真实长度len，起始下标位置start=(pos-mx)/2，要获取真实回文串及从字符串s的start位置开始len长度

时间复杂度： O(n2)

二、Manacher算法核心 ​

通过暴力方法，以p字符为中心，已经进行扩大了，到p+1字符时又要重复的往外扩，通过Manacher优化这一点

1. 回文覆盖最右界r ​

回文覆盖最右界r就是以某个点为中心扩的时候，这个回文中心向右侧的延展区域恰好到达不了地方

text
s:   #   a   #   b   #   a   #   a   #   b   #   c   #
idx: 0   1   2   3   4   5   6   7   8   9   10  11  12

以idx为中心往外扩
idx=0 回文半径为1 到不了的地方就是r=1
idx=1 回文半径为2 [#a#]b r就是b的下标
idx=3 回文半径为4 [#a#b#a#]a r=7

只要r能够变得更大r就更新，比如在idx=3的时候r=7了，idx=4时r突破不了，当idx=6时r=8超过了7就突破了更新成8

2. 回文中心c ​

最早取得回文最右边界的开头位置，主要是最早，比如在idx=2，和idx=5时r都是9，那么c取最早的那个就是2

简单来说，是谁先让r突破更新的c就是谁

3. Manacher算法的加速过程 ​

当来到的中心点 i，利用 p、r、c 来进行回文扩展
a. i 没有被 r 包住，那么以 i 为中心直接扩展
b. i 被 r 包住，对称点 2c‑i 的回文半径，在大回文区域以内，直接确定 p [i] = p [2c‑i]

大回文：以c为中心、右边界为r的回文区间。
j=2c−i 是i关于中心c的镜像对称点。

text
当i被包住时，且在大回文区域内，根据对称性可以直接确定i的回文半径

（...,[...,2c-i,...],...,c...,【...,i,...】,...）
（）是c的回文半径包住了，由于在c的回文半径内，已知2c-i的回文半径，由于对称性，p[i]=p[2c-i]

c. i 被 r 包住，对称，2c‑i 的回文半径，在大回文区域以外，直接确定 p [i] = r ‑ i

text
[...,a(...,2c-i,...,b...],...,c...,d【...,i,...】）e
2c-i在回文串以外，i处的回文半径不能越过c的回文半径

反证法：已知a=b,b=d,a!=e，假设可以越过则d=e，所以有a=e,与a!=e矛盾，因此不成立，只能为 p[i] = r - i

如果可以越过则c的回文半径还可以延伸，这是矛盾的

d. i 被 r 包住，对称点 2c‑i 的回文半径，撞线大回文区域的边界，从 r 之外的位置进行扩展

text
d相当于把c倒过来，还需要进行扩展，可能越过边界，但是至少是p[i]=r-i，从边界开始扩展，不需要重复扩展    `

时间复杂度分析 ​

时间复杂度： O(n)

很巧妙的把暴力方法从O(n2)，优化到O(n)

根据Manacher算法的加速过程可以看出，a和b点是对没有扩展到达地方进行扩展，复杂度为O(n)，b和c是对扩展过的地方直接得到回文半径，复杂度为O(1)

所以时间复杂度为O(n)

代码模板 ​

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

std::string expend(const std::string& s) {
    std::string res = "@#";
    for (int i = 0; i < s.size(); i++) res += s[i], res += '#';
    res += '%';
    return res;
}
int get_Manacher_mx(std::string& s){
    std::string t=expend(s);
    std::vector<int>p(t.size());//回文半径数组
    int mx=0;
    for(int i=1,r=0,c=0; i < (int)t.size() - 1; i++){
        p[i] = (r > i) ? std::min(p[2*c-i], r-i) : 1;
        while(t[i-p[i]] == t[i+p[i]]) p[i]++;
        if(i + p[i] > r){
            r = i + p[i];
            c = i;
        }
        mx = std::max(mx, p[i]);
    }
    return mx - 1;
    //return p
}