Manacher算法原理与实现

Manacher算法原理与实现

概述

Manacher算法是一种用于快速计算字符串中回文串长的算法,复杂度为O(n)。下面介绍该算法的原理及实现细节。

原理

我们从朴素地查找回文串开始,我们枚举回文串的回文中心,并向两边扩展,这种算法是O(n^2)的。我们来想一个问题,如果有串abcbaabcbaabcbaabcba,它本身是回文的,而子串abcba也是回文的,在寻找过程中,abcba可能会被多次遍历到。我们能否把已经找到过的abcba信息利用起来,优化算法呢。Manacher就实现了这种优化。
首先我们要对字符串进行一步处理,因为奇回文abcba和偶回文abba存在不同的模式,需要分别考虑,我们把字符之间都插入一个特殊字符,如#,就可以把偶回文也转化为奇回文的情况了,如abba$#a#b#b#a#。其中,字符串0位置的字符$是用来防止越界的。
这里给一个对齐表方便观察。

manacher - Manacher算法原理与实现

我们考虑在上面的例子中,#a#b#c#b#a#a#b#c#b#a#存在子回文串#a#b#c#b#a#,在下一次遇到该回文串的回文中心时,我们可以考虑在整个大回文串找到这个中心的对称点,就像这样:

#a#b#c#b#a#a#b#c#b#a#
     ^         ^

并把对称点的答案直接拿过来用。如果我们用mx代表当前极大回文串右端点,id代表当前极大回文串中心位置,p数组代表某个位置为中心的最长回文串半径,那么代码写出来应该是这样的:

if(i < mx) p[i] = std::min(p[2 * id - i], mx - i);

然后我们再来扩展修正这个p值,动态地维护当前极大回文串即可。
在处理过的串中p数组代表的半径,而我们发现p数组的值实际上为原串中该位置为中心的最长回文串长+1,因此可以这样直接计算出答案。

实现

本代码可以通过【P3805】【模板】manacher算法 – 洛谷一题。

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

const int MAXN = 22000005;

char s1[MAXN], s2[MAXN];
int n, tot, p[MAXN], mx;

inline int manacher() {
    s2[tot++] = '$'; s2[tot++] = '#';
    for(int i = 1; i <= n; i++) {
        s2[tot++] = s1[i]; s2[tot++] = '#';
    }
    int mxlen = 0, mx = 0, id;
    for(int i = 1; i < tot; i++) {
        if(i < mx) p[i] = std::min(p[(id << 1) - i], mx - i);
        else p[i] = 1;
        while(s2[i - p[i]] == s2[i + p[i]]) p[i]++;
        if(mx < i + p[i]) {
            id = i; mx = i + p[i];
        }
        mxlen = std::max(mxlen, p[i] - 1);
    }
    return mxlen;
}

int main() {
    scanf("%s", s1 + 1); n = strlen(s1 + 1);
    printf("%d", manacher());
    return 0;
}

参考资料



发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据