【学习笔记】Manacher

算法原理

首先将 s 处理为 #a#b#c#b#a# 的形式,方便同时统计长度为奇数或偶数的回文串。

d[i] 表示以 s_i 为对称中心所能扩展出的回文串个数,而manacher可以在线性时间内求出 d[1]\dots d[n]。下面为求解方法:

假设当前该求 d[i],且 d[1]\dots d[i-1] 均已求出。对于所有以 s_1\dots s_{i-1} 为对称中心的回文串,设 l,r 为这些回文串中右端点最靠右的串的左右端点。此时分两种情况:若 i>r,则暴力求解 d[i];若 i\le r,由回文串的性质,d[i] 至少为 \min(r-i+1,d[l+r-i]),然后再暴力扩展 d[i]。在求出 d[i] 之后,更新 l,r

由于每次暴力扩展,都会使 r 的值增加,可知总复杂度为 O(n)

Code

Luogu P3805 【模板】manacher算法

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 22000005

using namespace std;

int n;
int d[MAX_N];
char s[MAX_N];

void manacher(char *s, int n) {
    for (int i = 1, l = 1, r = 0; i <= n; i++) {
        int k = i > r ? 1 : min(r - i + 1, d[l + r - i]);
        while (s[i - k] == s[i + k] && i - k >= 1 && i + k <= n) {
            k++;
        }
        d[i] = k;
        if (i + k > r) {
            r = i + k - 1, l = i - k + 1;
        }
    }
}

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (int i = n; i >= 1; i--) {
        s[i * 2] = s[i], s[i * 2 + 1] = '#';
    }
    s[1] = '#', n = n * 2 + 1;
    manacher(s, n);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, d[i] - 1);
    }
    printf("%d\n", ans);
}
点赞

发表评论

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