Manacher

Manacher

参考：Manacher

模板题：P3805 【模板】manacher算法

用于求最长回文串，复杂度为(O(n))，其中d1[i]表示以 i 为中心的长度为奇数的回文子串，如aaa中，d1[0]=1,d1[1]=2，d2[i]表示以 i 为右中心的长度为偶数的回文子串，如baab中，d2[1]=0,d2[2]=2

马拉车算法的关键在于利用回文串的对称性减少了重复计算。

const int maxn=1e7+1e6+5;
int d1[maxn],d2[maxn];	//d1保存奇数回文串，d2保存偶数回文串
void manacher(string &s){
    //回文串的长为 2*d1[i]-1,2*d2[i]
    int n=s.size();
    for(int i=0,l=0,r=-1;i<n;++i){
        int k=(i>r)?1:min(d1[l+r-i],r-i);
        while(0<=i-k&&i+k<n&&s[i-k]==s[i+k])
            k++;
        d1[i]=k--;
        if(i+k>r)
            l=i-k,r=i+k;
    }
    for(int i=0,l=0,r=-1;i<n;++i){
        int k=(i>r)?0:min(d2[l+r-i+1],r-i+1);
        while(0<=i-k-1&&i+k<n&&s[i-k-1]==s[i+k])
            k++;
        d2[i]=k--;
        if(i+k>r)
            l=i-k-1,r=i+k;
    }
}