manacher-526互联

应用

O(n)求以每个节点为中心的回文串长度

原理

1、对S=“hshbvbhshb”，每个字符之间插入“#”，以便统一奇偶长度回文串。并在最前插入"$"，左右扩展边界时才不会访问到-1，右边不用是因为自带"\0"。得到T="$#h#s#h#b#v#b#h#s#h#b#"

2、定义p[i]为T中i位为中心回文串半径，注意回文串不包括边界的"#"。然后我们愉快地发现p[i]就是S中回文串长度，而起点就是(i-p[i]-1)/2

3、最最最重要：如何求p[i] 利用回文串对称性质

假设我们已经知道i位前的p[]，现回文串最右的右端点为R（注意R不在回文串中），其中心为C。i_m为i对于C对称点

若i不在C的回文串里，朴素

找到对称点回文半径3，那么i为回文半径至少为3，即至少有回文串"h#s#h"

为什么说至少：i回文右端"h"右接C的回文串外部，外部的情况是不确定的，是未知的。朴素地扩展一下，同时更新C，R

不至少的情况：i回文不右接外部，即p[i_m]<diff=R-i

上面说的至少也不准确，因为有i_m回文串超出C回文串的情况。因此p[i]至少为min(p[i_m],diff)

时间复杂度是怎么保证的呢？在每次朴素的时候，我们将R单调向右移动，最多移动n次

代码

const int MAX=2.2e7+10;
int p[MAX];
string s;
string pP(string s){//得到处理后字符串
    int n=s.length();
    if(!n)  return "$";
    string ret="$";
    for(int i=0;i<n;++i)
        ret+="#"+s.substr(i,1);
    ret+="#";
    return ret;
}string lP(string s){
    string T=pP(s);int len=T.length();
    int C=0,R=0;
    for(int i=1;i<len;++i){//忽略0位的"$"
        int i_m=C*2-i,diff=R-i;
        if(diff>=0){//i在C的回文串中
            if(p[i_m]<diff)  p[i]=p[i_m];
            else{//i_m回文超出或左接C回文
                p[i]=diff;
                while(T[i+p[i]+1]==T[i-p[i]-1]){
                    p[i]++;C=i;R=i+p[i];
                }//朴素扩展
            }
        }else{
            p[i]=0;
            while(T[i+p[i]+1]==T[i-p[i]-1]){
                p[i]++;C=i;R=i+p[i];
            }
        }
    }int maxl=0,cI=0;
    for(int i=1;i<len-1;++i)
        if(p[i]>maxl){maxl=p[i];cI=i;}
    return s.substr((cI-1-maxl)/2,maxl);
}//返回最长回文串

View Code

格式好像崩了，就这样吧