Manacher 学习

作用

线性时间解决最长回文子串问题。

思想

Manacher充分利用了回文的性质，从而达到线性时间。

首先先加一个小优化，就是在每两个字符（包括头尾）之间加没出现的字符（如#），这样所有字符串长度就都是奇数了，方便了很多。
abcde->#a#b#c#d#e#

记录p[i]表示i能向两边推（包括i）的最大距离，如果能求出p，则答案就是max(p)-1了（以i为中点的最长回文为2*p[i]-1，但这是加过字符后的答案，把加进去的字符干掉，最长回文就是p[i]-1）。

我们假设p[1~i-1]已经求好了，现在要求p[i]：

假设当前能达到的最右边为R，对应的中点为pos，j是i的对称点。

1.当i＜R时

由于L~R是回文，所以p[i]=p[j]（i的最长回文和j的最长回文相同）。

这种情况是另一种：j的最长回文跳出L了。那么i的最长回文就不一定是j的最长回文了，但蓝色的肯定还是满足的。

综上所述，p[i]=min(p[2*pos-i],R-i)。
2.当i>=R时
由于后面是未知的，于是只能暴力处理了。

效率

复杂度是 O（n）的

因为R不会减小，每次暴力处理的时候，p[i]增大多少，就说明R增大多少，而R最多增加len次。

核心代码：

void manacher() {

    now[0] = '$';

    for(ll i = 1; i <= 2*len; i += 2){

        now[i] = '#';

        now[i+1] = s[(i+1)/2];

    }

    now[2*len+1] = '#';

    now[2*len+2] = '@';

    now[2*len+3] = '\0';

    ll len2 = len*2+1;

    ll mx = 0, id = 0;

    for(ll i = 1; i <= len2; i++){

        if (i <= mx) p[i] = min(p[2*id-i], mx-i);

        else p[i] = 1;

        while(i+p[i]<=len2 && i-p[i]>=1 && now[i-p[i]] == now[i+p[i]]) {

            p[i]++;

        } 

        if (mx < i+p[i]) {mx = i+p[i]; id = i;}

    }

}

巴特西

Manacher 学习

作用

思想

效率

最新文章

热门文章