manacher

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是更新right和num。

好那接下来就是manacher的核心了。what注释的那一行究竟有什么玄妙呢？
大家最好拿起笔和纸在不懂得地方自己画画看。
首先if的条件是扫描的右边界大于当前点，若不是则直接置初始值为1，很显然。
若是，则是以i为圆心的回文串已经有部分比较过（确定）了。
令$ j=num*2-i $。则i与j关于num对称。
而因为i在num的半径内，故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