标签manacher

如何用马拉车

概述

manacher是可以在$O(n)$的复杂度内求得一个字符串的最长回文子串的大小。


基本想法

  1. 枚举每一个点作为中心,计算出以此点为中心的最长半径,使得这个半径的串是个回文子串。

  2. 暴力有很多重复的计算(还不是废话) 。当从1到n枚举的时候,我们考虑当前已经匹配好的右端点最大的中心,如果当前枚举的点在这个范围内,我们根据回文串的对称的性质,可以找到它关于这个中心的对称点,然后这个对称点的值一定是计算好的,那么当前这个点的值可以直接赋值成为对称点的值和,这个中心所能覆盖的较小值.这样我们就简化了很多计算。

  3. 然后继续匹配,当可以匹配到的最右边的端点的比当前的要远,那么就更新之。

  4. 实上这个算法还需要一部预处理操作,我们将该字符串依次填充进’#’符号,这样就不用考虑其奇偶性。


复杂度

一种通俗的解释就是

两个指针必然有一个至少挪动一位,而且消耗时间和位移动成正比,而且不会向左移。

所以复杂度是线性的


板子

UPD at 2018.7.6 修改了码风和变量名

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 11000029;
char c[N], s[N << 1];
int r[N << 1];
int len, ans;

void manacher() {
    int MaxRight = 0, mid;
    for(int i = 1; i < len; ++i) {
        if(MaxRight > i)
            r[i] = min(r[2 * mid - i], r[mid] + mid - i);
        else r[i] = 1;
        for(; s[i + r[i]] == s[i - r[i]]; ++r[i]);
        if(r[i] + i > MaxRight) {
            MaxRight = r[i] + i;
            mid = i;
        }
    }
    int res = 1;
    for(int i = 0; i < len; ++i)
        res = max(res, r[i]);
    res -= 1;
    printf("%d\n", res);
}

void init() {
    s[0] = s[1] = '#';
    for(int i = 0; i < len; ++i) {
        s[i * 2 + 2] = c[i];
        s[i * 2 + 3] = '#';
    }
    len = len * 2 + 2;
    s[len] = 0;
}

int main() {
    scanf("%s", c);
    len = strlen(c);
    init();
    manacher();
    return 0;
}