manacher

本文主要是介绍manacher，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

manacher

快速求最长回文串的方法。

• \(hw\) 数组表示 \(i\) 能扩展出的回文串长度（只有半边
• \(mr\) 已知回文串最右边的结束位置
• \(mid\) \(mr\) 所在的最长回文串的中心位置

代码核心思想就是通过 \(mid\) 和 \(mr\) 不断往右扩展，这样时间和空间都是线性的，利用了回文串对称的性质。在预处理时将字母与字母之间用 # 隔开，记得维护数列对称性质！

比 \(mr\) 大的 \(i\) 已经处理过了...直接赋值为 \(1\) 就好。

#include <bits/stdc++.h>
#define ll int
#define maxn 20000001
using namespace std;
ll len,ans,hw[maxn<<1];
char s[maxn],t[maxn<<1];

inline void manacher(){
    ll mr=0,mid=0;
    for(register int i=1;i<len;++i){
        if(i<mr)
            hw[i]=min(hw[mid*2-i],hw[mid]+mid-i);
        else
            hw[i]=1;
        while(t[i+hw[i]]==t[i-hw[i]])
            ++hw[i];
        if(hw[i]+i>mr)
            mr=hw[i]+i,mid=i;
    }
}

int main(){
    cin>>s;
    len=strlen(s);
    t[0]=t[1]='#';
    for(register int i=0;i<len;++i){
        t[i*2+2]=s[i];
        t[i*2+3]='#';
    }
    len=len*2+2;
    t[len-1]='#';
    manacher();
    ans=1;
    for(register int i=1;i<len;++i)
        ans=max(ans,hw[i]);
    printf("%d\n",ans-1);
    return 0;
}

这篇关于manacher的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！