manacher小结

P3805 【模板】manacher算法

题目大意

$O$$($$n^3$$)$

枚举两端点，暴力往中间搜

$O$$($$n^2$$)$

枚举回文串终点，暴力往两边搜

$O$$($$n$$)$

$first：$

$j$与$i$关于$pos$对称，$S$为以$pos$为中间的回文串，$Maxright$为$S$的右端点，$s_1$为以$j$为中间的回文串

$s_2$为以$i$为中间的回文串

下面开始将$manacher$，要降低复杂度，就要减少重复的操作

$（1）$ $s_1$被$S$包含（且没到端点）

显然根据回文的性质$len_{s_1}$=$len_{s_2}$

$（2）$  $s_1$超过或触及端点

这时，我们只能确定，两条蓝线之间的部分（即不超过$Maxright$的部分）是回文的

于是从这个长度开始，从$i$的左右两边搜一遍，当左右字符不同，或者到达边界时停止

$（3）$ 当$i$在$Maxright$的右边

$s_2$还没有任何部分被访问过，只能从$i$的左右两边搜一遍，当左右字符不同，或者到达边界时停止

ps:记得要时刻更新$Maxright$和$pos$

My complete code:

#include<cstdio>

#include<cstring>

using namespace std;

int n,ans; int hw[22000010];

char a[11000010],s[22000010];

inline int MIN(int g1,int g2){

    return g1<=g2?g1:g2;

}

inline int MAX(int g1,int g2){

    return g1>=g2?g1:g2;

}

inline void change(){

    s[0]=s[1]='#';

    for(int i=0;i<n;i++){

        s[i*2+2]=a[i];

        s[i*2+3]='#';

    }

    n=n*2+2;

    s[n]=0;

}

inline void manacher(){

    int maxright=0,mid=0;

    for(int i=1;i<n;i++){

        if(i<maxright)

            hw[i]=MIN(hw[(mid<<1)-i],maxright-i);

        else

            hw[i]=1;

        while(s[i+hw[i]]==s[i-hw[i]])

            ++hw[i];

        if(hw[i]+i>maxright){

            maxright=hw[i]+i;

            mid=i;

        }

    }

}

int main(){

    scanf(" %s",a);

    n=strlen(a);

    change();

    manacher();

    for(int i=0;i<n;++i)

        ans=MAX(ans,hw[i]);

    printf("%d",ans-1);

    return 0;

}