Manacher

Posted by JU on May 13, 2018

Manacher

Step 1

为了使对称轴不会形成在两个字符之间,在每两个字符之间插入一个#。

Step 2

记目前右端距离开头最远的回文串。
该串:dic(其实没啥用)
该串的对称轴:pos
串的最右端:right
i个字符为对称轴的最长回文子串长度:p[i]

Step 3

枚举到对称轴i,有两种情况:
1.i>=right,不能从之前的信息中得到有用东西,p[i]=1
2.i< right,可知idic中对称的位置为pos*2-i
这个位置已经计算过,因此可加以利用。
当对称轴为pos*2-i的回文子串被pos串覆盖,p[i]=p[pos*2-i]
否则p[i]=right-i
结论:p[i]=(i>right)? 1 : min (right-i,p[pos*2-i]);

Step 4

暴力扩展。
更新dic

Code

int init ()
{
	int len=strlen (tmp),j=1;
	s[0]='!',s[1]='#';
	for (int i=0; i<len; i++)
		s[++j]=tmp[i],s[++j]='#';
	s[++j]='$';
	return j;
}
int manacher()
{
    int len=init ();
    int pos=1,right=1,ans=-1;
    for (int i=1; i<len; i++)
    {
        p[i]=(i>=right) ? 1 : min (right-i,p[(pos<<1)-i]);
        while (s[i-p[i]]==s[i+p[i]]) p[i]++;
        if (right<i+p[i]) pos=i,right=i+p[i];
        ans=max (ans,p[i]-1);
    }
    return ans;
}

时间复杂度

$O(n)$

LuoguP4555 先跑一遍马拉车,跑的时候记录两个数组:
ll[i]表示以i为结尾的最长回文串长度,
rr[i]表示以i为开头的最长回文串长度。

void manacher()
{
    len=init ();
    int pos=1,right=1;
    for (int i=1; i<len; i++)
    {
        p[i]=(i>=right) ? 1 : min (right-i,p[(pos<<1)-i]);
        while (s[i-p[i]]==s[i+p[i]]) p[i]++;
        if (right<i+p[i]) pos=i,right=i+p[i];
        ll[i+p[i]-1]=max (ll[i+p[i]-1],p[i]-1);
        rr[i-p[i]+1]=max (rr[i-p[i]+1],p[i]-1);
    }
}

注意这会导致部分本应有值的位置为0
因为这些位置所在回文串被另一个(更长)覆盖。
于是还需要简单递推一下。

for (int i=1; i<=len-1; i+=2) rr[i]=max (rr[i],rr[i-2]-2);
for (int i=len-1; i>=1; i-=2) ll[i]=max (ll[i],ll[i+2]-2);

又注意只选择串中为’#’的位置递推,这可保证不重复计算。

CC 原创文章采用CC BY-NC-SA 4.0协议进行许可,转载请注明:“转载自:Manacher