manacher:$ O(n) $找出最长回文子串


其实上学期为了考NOIP PJ的时候研究了下这东西。感觉并不是十分难懂吧。
本来打算考KOI之前复习一下,结果忘了,结果真的用得上……
嘛。现在复习也不迟也不迟。


特别重要一件事

manacher怎么读呢?
来跟我一起读:么~呢~希尔。
其它读法都是异教徒。举起手中的火把烧死他们!


预处理

那么开始了。
首先我们匹配回文串,就不得不考虑这个回文串的长度是奇数的,还是偶数的。
换言之,回文串的对称点是在某一个字符或是在某两个字符的中间。
若使用类似动规或者暴力匹配恐怕这问题得纠结一会儿?
所以manacher就直接把这些空格用一个分隔符代替,其中分隔符不在字符串集内,例如“!@#$%^&*-+_=`~;':"[]{},./<>?”在字符串只是字母的时候就可以拿来当分隔符。

例子:abba;aba
插入分隔符后:#a#b#b#a#;#a#b#a#

这样所有的回文串长度都会成为奇数。(l->2l+1)
简单的实现:

void init()
{
    for(int i = 0; i < length; i++)
    {
        b += '#';
        b += a[i];
    }
    b += '#';
    length = b.length();
}

接下来才是重头戏。


manacher

void manacher()
{
    memset(r, 0, sizeof(r));
    int right = 0, num = 0;
    for(int i = 0; i < length; i++)
    {
        if(right > i)
            r[i] = min(r[num * 2 - i], right - i);//what?!
        else
            r[i] = 1;
        for(;
            i - r[i] >= 0 && i + r[i] <= length && b[i - r[i]] == b[i + r[i]];
            r[i]++);
        if(r[i] + i > right)
        {
            right = r[i] + i;
            num = i;
        }
    }
}

首先做一些定义。
r[i]表示以i为对称点的最长回文子串的半径,包括自身,故扫描过的r[i]均大于零。
right表示当前所有回文串中,最右端的位置,num表示right是以s[num]为圆心的回文串的子字符。

我们认为,循环内第一个if-else可以借助当前扫描过之字符对r[i]赋一个初值,也就是确保接下来将不会进行任何与之前重复的比对,确保时间复杂度为$ O(n) $。
之后的for和暴力长的一样,注意边界判定。
接下来的if是更新rightnum

好那接下来就是manacher的核心了。what注释的那一行究竟有什么玄妙呢?
大家最好拿起笔和纸在不懂得地方自己画画看。
首先if的条件是扫描的右边界大于当前点,若不是则直接置初始值为1,很显然。
若是,则是以i为圆心的回文串已经有部分比较过(确定)了。
令$ j=num*2-i $。则i与j关于num对称。
而因为inum的半径内,故j也在该半径内,而num的半径内是回文的,所以当j的回文范围不越过num的边界,自然而然有$ r[i]\ge r[j] $。
但是j越过边界怎么办呢?注意到了min函数后面还有个right-i了吗?
可以发现,没有任何一组是重复扫描回文串的。时间复杂度自然而然也是线性时间。


时间复杂度的证明

<s>看咱那么懒……</s>完整证明就不用了吧……
不,为了锻炼大家的思维,大家自己给出完整证明吧。欢迎投稿。


参考

http://blog.csdn.net/ggggiqnypgjg/article/details/6645824/
我就不吐槽那里的代码风格了。


代码下载

Manacher.cpp

标签: manacher

已有 2 条评论

  1. 没看懂orz

添加新评论