高铁拉我，马拉车——记高铁路上的manacher

• 前言
• 问题引入
• 思路一览
• manacher高效的原因
• 具体情况讨论
• 小问题的讨论
• code

前言

不得为什么，总会在奇奇怪怪的时候特定时间看算法比平常看得舒服多了，之前看字符串匹配的时候自然是准备把马拉车一起看了的，但是那时候看不下去，昨天回家的高铁上再次看了看，觉得格外的亲切，emmm

问题引入

对于一个字符串，要求求出最长的回文子串，如何操作

思路一览

• 找出字符串的所有字串，判断是否是回文串，时间复杂度是n²*n=n³
• 对于每一个字符进行中心扩展，时间复杂度是n²
• 还有一个是二分加哈希的做法，不过不太了解，私密马赛，时间复杂度是nlog_n
• 最后一个就是本文记录的manacher算法，可以在线性时间内解决该问题，也就是说，时间复杂度达到了n

manacher高效的原因

回文串中的镜像也是回文串，简化了中心扩展的次数

以上图为例，现在要求以点i为中心的最长的回文半径，那么i之前的点最长的回文半径已求出（这句话是不是听起来有一点点的耳熟），我们假设在前面点的记录的最长的回文半径中心是mid，lt和rt分别是它的左右边界，以mid为对称中心，i的对称点为j，我们就可以通过j的状态来推i的状态（这下更熟了吧，这不就是dp嘛，emmm）

具体情况讨论

• i在rt内
  • j_lt > mid_lt
    
    根据回文串的对称性，那么i的回文串长度和j的回文串长度一样
  • j_lt <= mid_lt
    
    这种情况最多只能得出mid回文串内的部分是可以回文的，其余部分就要继续扩展了
• i在rt外
  
  此时rt外的部分并没有扩展，因此只能确定i该点是回文的，其余部分需要向外扩展

小问题的讨论

可以看出，manacher算法是对中心扩展的一种改进，但是问题来了，中心扩展好像只对奇回文子串好使，如aba可以从b开始扩展，但是abba是怎么样扩展而来的的呢，因此这个好像就不适用了，我们就要对原先的字符串进行一些改造，比如，在每个字符之间加入一些不可能出现在原字符串的内容，首尾也要加，这样就可以将原先的要讨论的奇偶性全部转化为奇了，例如#a#b#a#和#a#b#b#a#，个人倾向于再在首尾加上不同的特殊符号，防止溢出

code

//p数组用于存放回文串的长度
string change(string s) {
    int lth = s.size();
    string res;
    res += string("$#");
    for(int i=0; i<lth; i++) res += s[i], res += string("#");
    res += string("#");
    return res;
}
void manacher(string s) {
    int n = s.size();
    //mid是当前最长回文串的中心结点，rt则是其右边界
    int mid = 0, rt = 0;
    for(int i=1; i<n; i++) {
        //这里分别是两种情况，一种是可以找到对称点，一种是不可以
        p[i] = (i >= rt) ? 1 : min(p[(mid<<1) - i], rt - i);
        while(s[i+p[i]] == s[i-p[i]]) ++p[i];
        if(i+p[i] > rt) {
            //更新结点操作
            mid = i;
            rt = i + p[i];
        }
    }
}