Chlience

【算法】回文串之 Manacher 算法
背景总所周知, Manacher 算法是用来解决最长回文问题的,使用此算法,可以将一般的 $O(n^2)$ 复杂度...
扫描右侧二维码阅读全文
13
2018/10

【算法】回文串之 Manacher 算法

背景

总所周知, Manacher 算法是用来解决最长回文问题的,使用此算法,可以将一般的 $O(n^2)$ 复杂度降低到线性 $O(n)$

那么 Manacher 算法的原理到底是什么呢?

算法过程

首先,由于回文分为 奇回文偶回文 (以某个字母或者某个空腔为对称轴),在原串中插入无用字符来将其转化为奇回文问题,同时,为了防止越界,一般我们在头部也插入一个无用字符

原串:        a b a b b a a b
修改后:    $ a # b # a # b # b # a # a # b

定义一个辅助数组 $p[i]$ 代表第 $i​$ 个位置为中心的最长回文半径

比如

pos01234567891011121314151617
char.#a#b#a#b#b#a#a#b#
p.12141412521252121

由于最终答案要去掉特殊符号 ,观察发现 $p[i] - 1$ 即为位置 $i$ 的点作为对称轴时在原串的最长回文长度

那么问题就转化为了求 $p$

发现如果一个点被包含在一个回文串之中,我们可以直接利用会回文串对称的性质直接转移得到该点的 $p$ ,从而降低复杂度,具体怎么做呢?

设置两个变量, $r$ 表示当前已得到的回文串覆盖最右位置, $pos$ 表示覆盖最右位置回文串的对称轴, 同时将回文串的左侧位置 $l$ 也画出来

manacher1

设当前处理到位置 $i$ ,显然 $i$ 应该在 $pos$ 的右侧,同时最多到达 $r + 1$ 位置

  • 若 $i \leq r$ ,得到 $i$ 关于 $pos$ 对称的位置 $i'$

    • 若 $i'$ 为对称轴的回文串完全在 $l$ 右侧,那么 $i$ 为对称轴的回文串应该完全与其对称,即 $p[i] = p[i']$
      manacher2
    • 若 $i'$ 为对称轴的回文串到达了 $l$ 甚至越过了 $l$ ,可以发现只能够确定对称部分的回文,而超过 $r$ 的部分则需要向右拓展,同时更新 $r$ 和 $pos$
      manacher3
  • 若 $i = r + 1$ ,发现对称部分完全没有用么(雾

    • 直接向右拓展,同时更新 $r$ 和 $pos$

通过 Amortized Analysis 我们可以得出每个点只有在被扩展时做出贡献,而每个点仅仅被扩展一次,所以时间复杂度为 $O(n)$

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 11000010;
char s[N];
char str[N << 1];
int top , p[N << 1];
int main() {
    scanf("%s" , s);
    int n = strlen(s);
    str[top] = '$';
    str[++ top] = '#';
    for(int i = 0 ; i < n ; ++ i) {
        str[++ top] = s[i];
        str[++ top] = '#';
    }
    int r = 0 , pos = 0 , ans = 0;
    for(int i = 1 ; i <= top ; ++ i) {
        if(i < r) p[i] = min(p[pos * 2 - i] , r - i);
        else p[i] = 1;
        //区分 p[i] 需要开始拓展的位置
        //若超过,先将其设为 r - i ,使其自行扩展,同时为了代码更加精简,未超过时我们也使其进行扩展
        while(str[i + p[i]] == str[i - p[i]]) ++ p[i];
        //向外拓展
        if(i + p[i] > r) {r = i + p[i]; pos = i;}
        ans = max(ans , p[i] - 1);
        //更新 r , pos , ans
    }
    printf("%d\n" , ans);
    return 0;
}
Last modification:January 21st, 2019 at 09:33 am

Leave a Comment