欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

回文自动机 学习笔记

程序员文章站 2022-06-10 22:19:20
...

  Manacher解决的问题:O(n)时间内求出字符串以每个点为中心时的最长回文长度

  1.对字符串的预处理

  一般为了避免无限制的匹配下去,会在开头和结尾加入未在原字符串中出现的‘#’

  一般为了方便判断,一般在原字符串的字符之间加入未在原字符串中出现的‘#’,

  新串由两部分组成,新加入的‘#’字符的个数就是len[原串]+1,原字符串为len[原串],所以

  这样新串的所有回文串的长度都变成了奇数,并且原回文的长度为(新串回文半径 - 1)

  2.定义len[]

  这里定义len[i]代表新串中的回文半径,len[i]-1就代表了原串中的回文长度,这样问题就转化为了求len[]

回文自动机 学习笔记

  3.如何在线性时间内求解len[]

  对len[]的计算按照从左往右一次进行,在计算len[i]时,len[j](j∈[0,i-1])都是已知的。

  这里维护一个MaxR,代表j+len[j]-1(j∈[0,i-1])的最大值,即在[0,i-1]计算过程中右端点的最大值

  同时维护取得最大值的位置,记为P。MaxR关于P的对称点记为MaxR`,i关于P的对称点记为j。

  可能出现的情况有三种:

  ① i <= MaxR && len[j] + i - 1 < MaxR

  由对称性可知len[i] = len[j]

回文自动机 学习笔记

 ② i <= MaxR && len[j] + i - 1 >= MaxR

  此时以i为中心的回文串可能会延伸到MaxR的右边,所以要从P开始匹配,匹配完成后更新变量

回文自动机 学习笔记

  ③ i > MaxR

  此时无法利用P的回文串,直接对于以i为中心的串暴力匹配,匹配完成后更新变量

  4.例题POJ-3974

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

using namespace std;

const int maxn = 1000000 + 10;

char s1[maxn], s2[maxn * 2 + 10];//s1原串,s2新串
int l, len[maxn * 2 + 10];

void init()
{
	l = 0;

    int n = strlen(s1);

    s2[++l] = '#';
    s2[++l] = '#';
    for (int i = 0; i < n; i++)
    {
        s2[++l] = s1[i];
        s2[++l] = '#';
    }

    s2[l + 1] = '\0'; // 结束字符
}

inline void manacher()
{
    int MaxR = 0, P = 0; // 定义MaxR与P
    for (int i = 1; i <= l; i++)
    {
        int now_len;//当前位置的len
        if (MaxR < i) now_len = 1; //如果是第③种情况
        else now_len = min(len[P * 2 - i], MaxR - i); //第①②种情况

        // 逐位匹配在第①种情况下是不会进行的,仅在②③种情况下进行,由对称性决定
        while (s2[i + now_len] == s2[i - now_len]) ++now_len;

        // 更新最右点
        if (i + now_len > MaxR)
        {
            MaxR = i + now_len;
            P = i;
        }

        len[i] = now_len;
    }
}

int main() {
    int T = 0;
    while (scanf("%s", s1), memcmp(s1, "END", 4) != 0)
    {
        init();
        manacher();
        int ans = 0;
        for (int i = 1; i <= l; i++) ans = max(ans, len[i] - 1);
        printf("Case %d: %d\n", ++T, ans);
    }

    return 0;
}

 

  

 

  

  

相关标签: Manacher 字符串