manacher算法笔记

part 1 算法简述

该算法由 Glenn K. Manacher 在 1975 年提出，是一种可以在O(N)时间复杂度下求字符串所有回文子串的算法，也是求最大回文子串最高效的算法。该算法的难度主要在于理解。

part 2 算法详解

求最大回文字串，首先要注意奇回文串与偶回文串的区别，如果不进行处理统一，就会使代码变得很复杂。

那么怎么来统一呢？

可以在每两个字符之间加上字符串中不曾出现的字符（包括头和尾），这样就可以使得字符串长度变为奇数，原因如下：

\(设原字符串长度为k,则经过操作后变为2k+1,必定为奇数.\)

例如：

解决了字符串统一的问题，接下来需要思考怎么优化求最大回文字串的过程。（\(O(n^2)\)的暴力算法在此不做介绍）

按照以往的经验，减少求回文的次数是关键，我们需要尽量使用已经拥有的数据。

此处分成两种情况：

• 1. 当前枚举的回文中心点在最大回文串内。

  这种情况，是最简单的情况，我们可以运用回文的对称性，使用大回文串的另一边的对称点的数据。当然，万一可以更大呢？所以还是要在该数据的基础上继续尝试扩张。

• 2. 当前枚举的回文中心不在最大回文串内。

  那就调用朴素算法进行计算。

part 3 代码实现

模板题：HDU 3068 最长回文

#include<bits/stdc++.h>
using namespace std;
char a[1100010];
char b[1100010];
long long ln;
void chuli(){//对字符串进行处理
    ln=0;
    b[ln++]='@';
    long long lenn=strlen(a);
    for(long long i=0;i<lenn;i++){
        b[ln++]='#';
        b[ln++]=a[i];
    }
    b[ln++]='#';
}
long long len[1100010],ans;
void huiwen(){
    memset(len,0,sizeof(len));
    long long p=0,po=0;
    ans=0;
    for(long long i=1;i<ln;i++){
        if(i<p){//分类讨论
            len[i]=min(len[2*po-i],p-i);
        }else{
            len[i]=1;
        }
        while(b[len[i]+i]==b[i-len[i]]){//尝试扩张
            len[i]++;
        }
        if(len[i]+i>p){//更新最大回文串
            p=len[i]+i;
            po=i;
        }
        ans=max(ans,len[i]);//更新答案
    }
}
int main(){
    while(~scanf("%s",a)){
        chuli();
        huiwen();
        printf("%lld\n",ans-1);
    }
}

part 4 参考文章

1.rwbyblake：manacher介绍及图文讲解（用于求解最长回文子串）
2.oi-wiki：Manacher