Manacher回文串匹配算法 学习笔记【Manacher】【字符串】

点击量：256

〇、前言

    感觉和KMP一样，理解起来不费劲，主要是实现方式与原理掌握了应该就不难了。（毒奶

一、引入

回文串

    回文串，即这个字符串正着读和反着读一模一样，例如aba是一个回文串，而asdfghjkl不是，gg是一个回文串，而wjyyy不是。

\(O(n^3)\)求回文串

    首先用\(O(n^2)\)枚举出所有子串，然后\(O(n)\)扫描判断其是不是回文串，可以用两个指针分别从中间向两边扫，看是否有不同的元素。

\(O(n^2)\)求回文串

    可以看出，一个长为\(l(l\ge 3)\)的回文串去掉两端之后它仍然是一个回文串。为了省去不必要的枚举，我们只需要找出以每个位置为中点能扩展出的回文串长度。首先枚举中点，然后枚举半径，如果半径再扩展一位仍然相等，那么令半径\(+1\)，否则把中点移到下一位继续枚举。这样枚举时间复杂度是\(O(n^2)\)的了。

\(O(n\log n)\)求回文串

    因为回文串正着读和反着读一样，所以选定它的中点，这个回文串就关于这个中点对称，也就是要求左边一段翻转后等于右边一段。这时我们可以用万能的hash，hash甚至可以替代KMP，为什么不能用来求回文串呢？如果要判断左边一段翻转后等于右边一段，那么只需要预处理出正反两个方向的hash值，然后分别取出来一段判断是否相等，但是枚举还是\(O(n^2)\)的啊。要知道，当一个串不合法时，左右两段是不相等的，如果一个半径为\(r\)的串都不合法，那么如果再扩展它到\(r+1\)，也是不合法的。因此这个条件是单调的，我们可以二分哈希值相等的位置，这样就可以判断了。

二、Manacher算法

概述

    Manacher算法可以在\(O(n)\)的时间复杂度内完成求最长回文串的工作，它的思路和KMP类似，排除了冗余的枚举，相当于一个点只被更新一次。

原理

    因为回文串是对称的，所以这个回文串左边有什么性质，右边也会有。如果回文串的左边是一个子回文串，那么这个子回文串中点关于长回文串中点对称的位置一定也有那样的性质。

    比如说以第四个位置上的\(\tt c\)为中点，因为位置\([1,3]\)是一个回文串，那么\([5,7]\)一定也是个回文串。因此当我们已知以\(4\)为中点有一个回文串时，\(4\)位置的右边可以直接利用\(4\)左边的信息，我们设以第\(i\)个点为中点的回文串半径是\(len[i]\)，这个回文串的长度就是\(2len[i]-1\)。在上述例子中，因为\(len[2]=2\)，那么\(len[6]\)至少为\(2\)，所以枚举以\(6\)为中点的回文串，长度可以从\(3\)开始尝试。

    但是我匹配的时候怎么能知道这个字符串在哪个回文串里呢？我们需要用一个\(mr\)来存当前已经扩展到的最右位置，也就是目前已知最大的右端点，同时用一个\(md\)来存这个右端点对应的中点。

    此时我们发现一个问题，就是一个回文串长度可能为奇，也可能为偶，对称轴/中点不好统一。我们可以在每两个字符之间插入一个题目中不可能出现的字符，常用的有#,$等，这样所有回文串都是奇串了。原来的奇回文串在这里的中点是一个字母，原来的偶回文串在这里的中点是特殊符号（下文定为#）。

    继续考虑回文串匹配的问题。假设当前枚举到的下标是\(i\)，如果\(i\le mr\)，那么就可以直接对称过去，这里要注意一点，这个点和对称点尽管可以互相利用\(len\)数组，但是它们不一定等价。也就是说，对称过去的另一端可能可以扩展到更远的回文串，导致这一端\(i+len[i]\)超过了\(mr\)。而因为之前在\(md\)处扩展到\(mr\)就不能扩展了，说明这一边和那边不相等，因此这边的\(i+len[i]\)要控制在\(mr\)以左。

    如果\(i>mr\)，说明这里还没有被扩展到，这种情况一定满足\(i=mr+1\)，这时我们直接从\(i\)开始从\(len[i]=1\)枚举就好了。

分析

    为什么这个过程复杂度是(O(n))的呢？因为(mr)最多被移动(n)次，如果(i+len[i]<mr)，连(mr)都匹配不到，则(len[i])不会再扩展，不对复杂度造成影响；如果(i+len[i]\ge mr)，可以继续扩展，每次扩展都会让(mr+1)。因此总共(i)移动(n)次，(mr)移动(n)次，时间复杂度(O(n))。

三、Manacher算法的实现

初始化

    首先我们把所有的字符串前后都插入一个#，如abacabadbc\(\rightarrow\)#a#b#a#c#a#b#a#d#b#c#。但是处理完这个后，我们前后各多看一位会发现，\(0\)号位和最后一位都是缺省值\0，即\0#a#b#a#c#a#b#a#d#b#c#\0。此时\0也可能被算入回文串中，因此我们把字符数组的第\(0\)位置为一个不同于#的不可能用到的字符，如%。

处理

    在做完Manacher之后，每个位置会有一个\(len\)值。它表示了中点到其中一个端点（含）之间一共有多少个字符，可以发现，这一部分要么是#x#x#（x代表任意其他字母），\(len=5\)，此时回文串长度为\(4\)；要么是x#x#x#，\(len=6\)，此时回文串长度为\(5\)。因为一共两种情况，我们都枚举了，那么答案就是\(\max\limits_{1\le i\le 2n+1}len[i]-1\)了。

代码

洛谷P3805 【模板】manacher算法 \(strlen\le 11000000\)

#include<cstdio>
#include<cstring>
char t[11111111],s[22222222];
int len[22222222],md=0,mr=0;
void upd(int x)//扩展的过程
{
    while(s[x+len[x]]==s[x-len[x]])
        ++len[x];
    if(mr<x+len[x])
    {
        mr=x+len[x];
        md=x;
    }
}
int main()
{
    scanf("%s",t+1);
    int n=0;
    for(int i=1;t[i]!='\0';++i)
    {
        s[i*2]=t[i];
        s[i*2-1]='#';
        n=i;
    }
    s[n*2+1]='#';
    s[0]='%';
    int ans=0;
    for(int i=1;i<=2*n+1;++i)
    {
        if(i>mr)
            upd(i);
        else
        {
            len[i]=len[2*md-i];
            if(i+len[i]>mr)//控制右端点不超过mr
                len[i]=mr-i;
            upd(i);
        }
        ans=ans>len[i]?ans:len[i];
    }
    printf("%d\n",ans-1);
    return 0;
}

四、例题

    丢一个裸题就跑。

SP7586 NUMOFPAL – Number of Palindromes

题目描述

给定一个长度不超过\(1000\)的字符串，求它包含几个回文串。

题解

    这个题好像是可以\(O(n^2)\)搞过的吧……但是拿来练Manacher了。

    对于处理后的字符串，枚举中点为#，说明是偶回文串，\(len\)代表的是#x#x#，还原后是#x#x#x#x#，回文串个数为\(2\)（\(len\)中有两个字符x）\(=\frac{len-1}2\)；枚举中点为x，说明是奇回文串，\(len\)代表的是x#x#x#，还原后是#x#x#x#x#x#，回文串个数是\(3\)（\(len\)中有三个字符x）\(=\frac{len}2\)。

    综上所述，枚举每个位置，包括#，求出\(\sum_{i=1}^{2n}\left\lfloor\frac{len}2\right\rfloor\)即可。

Code

#include
#include
char t[1050],s[2050];
int len[2050],md=0,mr=0;
void upd(int x)
{
    while(s[x+len[x]]==s[x-len[x]])
        ++len[x];
    if(x+len[x]>mr)
    {
        mr=x+len[x];
        md=x;
    }
}
int main()
{
    scanf("%s",t+1);
    int n;
    for(int i=1;t[i]!='\0';++i)
    {
        s[2*i]=t[i];
        s[2*i-1]='#';
        n=i;
    }
    s[2*n+1]='#';
    s[0]='%';
    for(int i=1;i<=2*n;++i)
        if(i>mr)
            upd(i);
        else
        {
            len[i]=len[2*md-i];
            if(i+len[i]>mr)
                len[i]=mr-i;
            upd(i);
        }
    int sum=0;
    for(int i=1;i<=2*n;++i)//在这计算就好了
        sum+=len[i]>>1;
    printf("%d\n",sum);
    return 0;
}