Manacher算法学习笔记

时间：2022-12-26 10:42:45

Manacher：一种能在\(O(n)\)的时间内求解一个字符串中最长回文串长度的算法

不过洛咕例题是真的少，加上模板也只有三道

问题：

给定一个字符串，求解其回文子串中最长的一个的长度。

几种暴力：

  • \(O(n ^ 3)\)

依次枚举它的每一个子串，然后复制翻转一位一位进行判断（一看就很慢。抬走。）

  • \(O(n ^ 2)\)

    枚举对称轴并向两端扩展直到扩展到的两端点不相同，同时进行计数。
    咦好像优秀一点了？然而还是慢
    对于这个算法，我们分析它有主要的两个缺点：

    • 要判断奇偶
      比如"aabaa"的对称轴在"b"上，而"aabbaa"的对称轴在两个"b"之间的缝里导致游戏体验极差
    • 进行多次重复计算
      不难发现，在计算第\(i + 1\) 位时，我们左右扩展的范围大部分在计算第\(i\)位的时候都被判断过了一次，因此冗杂的计算耗去大量时间。

因此，Manacher算法是在第二种暴力的基础上进行了一定的优化和状态记录，实现用先前的状态更新当前状态，并在此基础上进行扩展的操作。

Manacher算法

Manacher算法依次遍历字符串中每一位，记当前遍历到\(i\)，记录以\(i\)为对称中心的回文串最大半径为\(R[i]\)（包含\(i\)自己）。在此之外，我们记录当前我们处理过的节点里，回文半径最大的对称中心为\(mid\)，其扩展到的最右端节点为\(Max\_right\)。容易得到\(i\)必定在\(mid\)右侧，则我们按照\(i\)和\(Max\_right\)的位置关系分情况进行转移：

  • \(i\)在\(Max\_right\)左侧：

    设\(i\)关于\(mid\)的对称点为\(j\)，不难得到\(j = (mid << 1) - i\) （自己算一下）
    Manacher算法学习笔记

    • 当\(j\)为对称中心的回文串在左端点范围内时，\(R[i]\)可以先直接被\(R[j]\)更新，然后再在此基础上左右扩展。
    • 当\(j\)为对称中心的回文串覆盖并超过了左端点时，由于在当前最长回文串（图中两红色块之间）内才有关于\(mid\)左右对称的性质，无法判断\(Max\_right\)右侧是否与对应左端点左侧仍然回文，此时将\(R[i]\)更新为\(Max\_right - i + 1\)，然后在此基础上左右扩展。

  • \(i\)在\(Max\_right\)右侧：

    无法利用先前扩展过的\(R\)数组更新\(R[i]\)，直接暴力扩展更新\(R[i]\)。

最后\(Max\ of\ R[i]\)就是当前字符串中最大的回文半径，则\(ans = (Max\_R[i] / 2) * 2 - 1 = Max\_R[i] - 1\)。

代码

#include<bits/stdc++.h>
#define N (11000000 + 10)
using namespace std;
int mid, max_right, R[2 * N], ans = -1, len;
char s1[N], s2[2 * N];
void pre() {
    s2[0] = s2[1] = '#';
    len = strlen(s1 + 1);
    for (register int i = 1; i <= len; i++) s2[i * 2] = s1[i];
    s2[2 * len + 1] = '#';
}
void extend(int p, int i) {
    int pos = i;
    while (s2[p - pos + 1] == s2[p + pos - 1]) ++pos;
    pos--; 
    R[p] = pos;
    if (max_right <= p + pos - 1) max_right = p + pos - 1, mid = p;
}
void manacher() {
    R[1] = 1, mid = 1, max_right = 1;
    for (register int i = 1; i <= 2 * len + 1; i++) {
        R[i] = 1;
        if (i <= max_right) {
            int j = (mid << 1) - i;
            if (R[j] <= mid - j + 1) {
                R[i] = R[j];
                extend(i, R[i]);
                ans = max(ans, R[i]);
            } else {
                R[i] = max_right - i + 1;
                extend(i, R[i]);
                ans = max(ans, R[i]);
            }
        } else {
                extend(i, R[i]);
                ans = max(ans, R[i]);      
        }
    }
}
int main() {
    scanf("%s", s1 + 1);
    pre();
    manacher();
    printf("%d", ans - 1);
}
标签：

相关文章