字符串-回文-Manacher算法

http://blog.csdn.net/zzkksunboy/article/details/72600679

https://segmentfault.com/a/1190000008484167

求最长回文长度的一个算法 O(n)

首先解决要判断奇字符偶字符的问题在每一个字符前加一个不可能在字符串中出现的字符再在字符串的末尾加一个

abcde -> $#a#b#c#d#e# $是为了防止越界

$p[i]$表示$i$能向两边推（包括$i$）的最大距离，如果能求出$p$，则答案就是$max(p)-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$时
由于后面是未知的，于是只能暴力处理了。

定义 $mx$ 为以$s-new[id]$为中心的最长回文最右边界，也就是$mx = id + p[id]$。$j$ 与 $i$ 关于 $id$ 对称，根据回文的性质，$p[i]$的值基于以下三种情况得出：

（1）$j$ 的回文串有一部分在 $id$ 的之外，如下图：

上图中，黑线为$ id $的回文，$i$ 与 $j$ 关于 $id$ 对称，红线为 $j$ 的回文。那么根据代码此时p[i]=mx-i，即紫线。那么p[i]还可以更大么？答案是不可能！

假设右边新增的紫色部分是p[i]可以增加的部分，那么根据回文的性质，a 等于 d ，也就是说 id 的回文不仅仅是黑线，而是黑线+两条紫线，矛盾，所以假设不成立，故p[i]=mx-i，不可以再增加一分。
（2）j 回文串全部在 id 的内部，如下图：

此时p[i]=p[j]，那么p[i]还可以更大么？答案亦是不可能！见下图：

假设右边新增的红色部分是p[i]可以增加的部分，那么根据回文的性质，a 等于 b ，，也就是说 j 的回文应该再加上 a 和 b ，矛盾，所以假设不成立，故p[i]=p[j]，也不可以再增加一分。
（3）j 回文串左端正好与 id 的回文串左端重合，见下图：

此时p[i]=p[j]或p[i]=mx-i，并且p[i]还可以继续增加，所以需要

while (s_new[i - p[i]] == s_new[i + p[i]])

    p[i]++;

int Init()

{

    int len = strlen(s);

    s_new[0] = '$';

    s_new[1] = '#';

    int j = 2;

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

    {

        s_new[j++] = s[i];

        s_new[j++] = '#';

    }

    s_new[j] = '\0';  //别忘了哦  

    return j;  //返回s_new的长度

}

int Manacher()

{

    int len = Init();  //取得新字符串长度并完成向s_new的转换

    int maxLen = -1;   //最长回文长度  

    int id;

    int mx = 0;

    for (int i = 1; i < len; i++)

    {

        if (i < mx)

            p[i] = min(p[2 * id - i], mx - i);  //需搞清楚上面那张图含义, mx和2*id-i的含义

        else

            p[i] = 1;

        while (s_new[i - p[i]] == s_new[i + p[i]])  //不需边界判断，因为左有'$',右有'\0'

            p[i]++;

        if (mx < i + p[i])  //我们每走一步i，都要和mx比较，我们希望mx尽可能的远，这样才能更有机会执行if (i < mx)这句代码，从而提高效率

        {

            id = i;

            mx = i + p[i];

        }

        maxLen = max(maxLen, p[i] - 1);

    }

    return maxLen;

}

巴特西

字符串-回文-Manacher算法

最新文章

热门文章