Manacher 算法

2014.12.14 16:58 Sun| 6 visits oi_2015| 2015_算法笔记| Text

转自章玄润神牛在石家庄二中培训(2014/7/19)时的课件。

章玄润当初讲的课想来必是极好的,可是当初的我除了听他讨论数论和hash的一些那啥的用途的片段之外,竟然一句也没有听懂……

暴力求回文子串

枚举回文串中心位置,暴力枚举回文串半径,时间复杂度 $\mathcal O(n^2)$ 。

Manacher算法

在求回文串之前,我们先将每两个字符间加入一个未在字符集中间出现过的字符。

例如:"abcbab"->"#a#b#c#b#a#b#"

回文串的长度可能是奇数或者偶数,即可能关于某个字符对称或者关于某两个字符中间的分割位置对称。加入分割字符后,可以保证所有的回文串都是关于某个字符对称的,即所有回文串的长度都是奇数。

  • 定义p数组,p[i]表示位置i为中心的最长回文串的半径。
  • 定义mx,表示已求出的p[i]中i+p[i]的最大值。
  • 定义id,表示mx最大的时候i的取值,即id+p[id]=mx。 i关于id的对称点为id-(i-id),以对称点id-(i-id)为中心的回文串,关于点id 对称后,是中心为i的回文串。 if(mx>i),p[i]=min(p[id-(i-id)],mx-i) else,p[i]=1 while(str[i-p[i]]=str[i+p[i]]) p[i]++ 用i+p[i]更新mx和id 如果p[i]++一定是需要更新mx的时候(否则一定可以通过关于 id对称的点的p[i]扩展到),而mx是一个单调递增的值,从0开始最大不会超过N,所以p[i]++的次数不会超过N次,总的复杂度是线性的。

另外,需要注意的是上述字符串长度和p数组长度均需要为原字符串长度的二倍。

代码实现

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 110010

int p[N*2];
char s[N*2],str[N];

int manacher(char str[],int len)
{
    s[0]='$'; s[1]='#';
    for(int i=0;i<len;i++)
        s[i*2+2]=str[i], s[i*2+3]='#';
    len=len*2+2;
    int id=0,maxp=0,re=0;
    for(int i=1;i<len;i++)
    {
        if(maxp>i) p[i]=min(p[id*2-i],maxp-i);
        else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]]) p[i]++;
        if(i+p[i]>maxp) maxp=i+p[i], id=i;
        re=max(re,p[i]);
    }
    return re-1;
}

int main()
{
    while(scanf("%s",str)!=EOF)
    {
        int n=strlen(str);
        memset(p,0,sizeof p);
        memset(s,0,sizeof s);
        printf("%d\n",manacher(str,n));
    }
    return 0;
}