Manacher | Axell's Blog

manacher算法

功能： 在O(n)的时间内，求出一个字符串的最长回文子串
思路： 利用已经求出的结果，求出之后的答案，降低时间复杂度，注意有个小技巧：可以插入一个原串中不存在的字符，以避免奇偶性判断
实现和证明： 见here

代码

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;

char s[1000005],ss[500005];
int n,cnt,p[1000005];

void solve(){
    memset(p,0,sizeof(p));
    int ans=0;
    n=strlen(ss+1);
    int cnt=1;
    s[0]=-1;
    s[1]='#';
    for (int i=1;i<=n;++i){
        cnt++;
        s[cnt]=ss[i];
        cnt++;
        s[cnt]='#'; //插入#号，方便求解
    }
    n=cnt;
    int nowr=0,nowi=0;
    for (int i=1;i<=n;++i){
        if (i<nowr) p[i]=min(p[nowi*2-i],nowr-i);
        else p[i]=1;
        while (i-p[i]>=1 && i+p[i]<=n && s[i+p[i]]==s[i-p[i]]) p[i]++;
        if (p[i]+i>nowr) nowr=p[i]+i,nowi=i;
        ans=max(ans,p[i]-1); //每次答案是向一侧可拓展长度-1，因为插入了#号
    }
    printf("%d\n",ans);
}

int main(){
    while (scanf("%s",ss+1)!=EOF) solve();
    return 0;
}

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Link to this article: https://blog.axell.top/archives/77/