Manacher 学习笔记

发表于 | 分类于 | | + s

模板及讲解

Manacher是什么

Manacher 算法是用于算一个字符串最长回文子串长度的一个算法，其时间复杂度为$O(n)$

Manacher的实现

例题：Luogu: (模板)manacher算法

给出一个只由小写英文字符组成的字符串S， 字符串长度为n，求S中最长回文串的长度

暴力

1、直接枚举区间判回文串，$O(n^3)$

2、由于回文串关于中间点/中间点的线，枚举对称轴向两边扩展分奇偶讨论即可，$O(n^2)$

Manacher

因为字符串有奇有偶，所以我们要进行操作免除奇偶性讨论，我们在0处加一个’\$’, 最后面加’\0’，中间每个字符之间加’#’，即可将除了头尾两个字符以外的字符串长度都变成奇数个。例如abca可以变为\$#a#b#c#a#\0’，则变为奇数个，对称中心为中间那个字符。
我们设$p_i$为以$i$为对称中心，最长的回文半径长度。#a#b#b#b#a#中间的字符的$p_i$值为6，则$p_i-1$的值是以$i$为对称中心的最长回文子串长度。设$mr$为回文串最右能触及到的地方，$pos$为这个回文串的对称中心位置。

步骤：1、给$p_i$赋初值 2、向两边扩展 3、更新$mr$和$pos$

给$p_i$赋初值, 下面分两种情况讨论；
1、$i$在$mr$左边

$j=2 \cdot pos - i $为$i$关于$pos$的对称点。

当$j$的回文子串很小不超过左半区间时，我们令$p_i=p_j$，如下图(根据对称性，$i$的回文子串一定包含$j$的回文子串)
Markdown

当$j$的回文子串很大超过左半区间时，我们只能确定$p_i=mr-i$
Markdown

2、$i$在$mr$右边
此时$i$没有对称的$j$给它赋值，只能$p_i=1$

然后扩展字符串，之后不要忘记更新$mr, pos$的值，因为我们要使得$mr$更大，才能更多调用$p_i=p_j$

代码

例题：Luogu: (模板)manacher算法

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 11000000 + 5;
char s_old[MAXN], s[MAXN * 2];//旧数组，新数组 
int n, cnt, pos, mr, p[MAXN * 2];//n，新数组长度cnt，pos，mr，以i为对称轴最长回文半径长度p 
int manacher() {
    int ret = 0;
    for (int i = 1; i <= cnt; i++) {
        if (i < mr) p[i] = min(p[2 * pos - i], mr - i); else p[i] = 1;//对称性继承 
        while (s[i + p[i]] == s[i - p[i]]) p[i]++;//向两边扩展 ，不用判边界因为 前有$后有\0
        if (i + p[i] - 1 > mr) mr = i + p[i] - 1, pos = i;//更新mr，注意用 i + p[i] - 1更新 
        ret = max(ret, p[i] - 1);//更新答案 
    }
    return ret;
}
void clean() {
    mr = -1, cnt = 1;
}
int solve() {
    clean();
    n = strlen(s_old), s[0] = '$', s[1] = '#'; 
    for (int i = 0; i < n; i++) s[++cnt] = s_old[i], s[++cnt] = '#';
    s[cnt + 1] = '\0';//处理字符串，前加$后加\0 
    printf("%d\n", manacher());
    return 0;
}
int main() {
    scanf("%s", s_old), solve();
    return 0;
}

常见题型

1、求最长回文子串
Q：给出一个只由小写英文字符组成的字符串S， 字符串长度为n，求S中最长回文串的长度
解：见解析
例题：Luogu: (模板)manacher算法

------ 本文结束 ------