Manacher

Andy_WA · 2025-02-21 22:56:47 · 算法·理论

Manacher 算法

Manacher 算法 是一个用来查找一个字符串中的最长回文子串(不是最长回文序列)的线性算法。它的优点就是把时间复杂度为 O(n^2) 的暴力算法优化到了 O(n)。首先先让我们来看看最原始的暴力扩展，分析其存在的弊端，以此来更好的理解 Manacher 算法。

暴力匹配

• 时间复杂度：O(n^3)。
• 思路：尺取每一段子序列，然后判断是否为回文子串。

优化暴力

• 时间复杂度：O(n^2)。
• 思路：枚举回文串的中点，依次向左右扩展。

  处理无法处理回文串为偶数的问题

  1. 设原字符串为 str_原= abbaa。
  2. 将 str_原 中包括头尾在内的所有字符间的间隔插入一个在原字符串内没有的字符，这里就如 #。
  3. 则 str_现= #a#b#b#a#a#。
  4. 先即可处理回文串为偶数的情况。

二分加哈希

• 时间复杂度：O(n~\log~n)。
• 思路：
  • 回文串的长度是奇数：\ 枚举回文中心 i，二分子串的半径 k ，找到最大使子串 [i-k,i+k] 是回文串的 k 。\ 其中判断子串 [i-k,i+k] 是回文串等价于判断 str 的两个子串 [i-k,i] 与 [i,i+k] 是否是相反的串；\ 而这等价于判断 str[i-k,i] 子串与反转字符串 rstr 的 [len - 1-(i+k),len - 1 - i] 子串是否是相同的（ [a,b] 在反转字符串中的位置为 [len - 1 -b, len -1 - a] ）。\ 因此只需要判断 H1[i-k…i] 与 H2[i-(i+k)…len-1-i] 是否是相等的即可。
  • 回文串的长度是偶数：\ 枚举回文空隙点，令 i 表示空隙点左边第一个元素的下标，二分子串的半径 l ，找到最大使子串 [i-k+1,i+k] 是回文串的 k 。\ 其中判断子串 [i-k+1,i+k] 是回文串等价于判断 str 的两个子串 [i-k+1,i] 与 [i+1,i+k] 是否是相反的串；\ 而这等价与判断 str 的 [i-k+1,i] 子串与反字符串 rstr 的 [len - 1 - (i+k),len - 1 - (i + 1)] 子串是否是相同的，因此只需要判断 H1[i-k+1…i] 与 H2[len - 1- (i+k)…len - 1- (i+1)] 是否相等即可

显然，前面都不是正题。

Manacher 算法

经典问题：P3805 【模板】manacher。

过程

Step. 1 输入及处理

1. 读入字符串 str_原。
2. 将 str_原 中包括头尾在内的所有字符间的间隔插入一个在原字符串内没有的字符。

Step. 2 从前往后推半径

修改好字符串后，我们开始正式操作。

在这之前，先定义几个概念：

• 半径 r：在 r?1 的范围内组成的字符串为回文串。一个中点可能会有超过一条半径，我们这里取最大的半径，即取最长的回文串。

• 最远扩展位置：这个中点的最大回文串的右端点，其对称点为这个中点的最大回文串的左端点。

维护 p_i

Manacher 算法需要维护最大回文半径。设以第 i 个字符为中点的最大回文半径。

从前往后计算 p_i。

假设我们已经计算完成了 p_1, p_2, p_3, \dots , p_{i-1}。在枚举 i 的过程中，我们维护 r 的最大区间 [l,r]，其中：

如何扩展

• 令 $p_i=1$，并暴力向两边扩展。
• 找到 $i$ 关于 $m$ 的对称点 $k$。

若 p_{2m-i}<r-i+1，令 p_i=p_{2m-i}。\ 若 p_k 对应的回文区间包含 l，令 p_i=p_{r-i+1}。\ 并继续暴力扩展。

若 i>r，令 p_i=1。\ 若 1 \le r，令 p_i=min\{p_{2m-i},r-i+1\}。\ 并继续暴力扩展。

正确代码

#include<bits/stdc++.h>
using namespace std;
const long long MaxN=2.2e7+10;
long long n;
long long jump[MaxN];
long long l=0,r=-1;
long long ans=1;
long long cnt=1;
char str[MaxN],x;
int main(){ 
    str[0]='#';
    x=getchar();
    while(x>='a' && x<='z'){
        str[cnt++]=x;
        str[cnt++]='#';
        x=getchar();
        if(x==EOF) break;
    }

    for(long long i=1;i<cnt;i++){
        if(i<r) jump[i]=min(r-i,jump[r-i+l]);
        while(str[i+jump[i]+1]==str[i-jump[i]-1]) jump[i]++;
        if(i+jump[i]>r) r=i+jump[i],l=i-jump[i];
        ans=max(ans,jump[i]);
    }
    cout<<ans<<endl;
    return 0;
}