Manacher学习笔记

目录

• code(伪)

Manacher算法 可在 (O(n))的时间内求出一个字符串以每个位置为中心的最长回文子串。

原理:根据之前预处理出的回文串长度求得新的回文串长度

我们可以通过在字符中加上'#'来避免长度为偶数回文串没有中心的问题

原串 = "abcd"; 变为
新串 = "#a#b#c#d#";
原串中长度为奇数和偶数的回文串的长度均变为奇数，且原串中回文串的长度为新串回文串半径减一。

设置两个状态 $max $ 和 (p) , (p) 表示当前已找到的回文串中，向右延伸最远的中心位置，$max $ 表示其右端点。

设 (r(i)) 表示（新串中）第 (i) 个位置的回文半径（回文串长度的一半，包括第 (i) 个字符）按从左到右的顺序求解，枚举到第 (i) 个字符时，分三种情况考虑：

设( j) 为( i) 关于 (p) 的对称点，即 (j = 2p - i)

(max < i​)，即向右延伸最远的回文子串（黑色）没有覆盖 (i​)，此时只有 (r(i) geq 1​)。

(max geq i) 且 (max - i geq r(j))，即向右延伸最远的回文子串（黑色）覆盖了 (i)，并且以 jj 为中心的最长回文子串完全与以 (i) 为中心的最长回文子串对称（蓝色），此时一定有 (r(i) = r(j))，即 (r(i) geq r(j))。

(max geq i) 且 (max - i geq r(j))，即向右延伸最远的回文子串（黑色）覆盖了 (i)，但没有覆盖以 jj 为中心的最长回文子串的对称位置串，所以 (r(i)) 只能取被覆盖的（黄色）一部分，即 (r(i) geq max - i)。

code(伪)

int len;
void prepare(){
    len = 0;
    s2[++len] = '%';
    for(int i = 0; i < s.size(); i++){
        s2[++len] = '#';
        s2[++len] = s[i];
    }
    s2[++len] = '#';
}
void manacher(){
    int mid = 0, rb = 0;
    //此处的rb是 真实值加一
    //回文串为(lb, rb) (lb, mid] = [mid, rb) 所以计算半径直接rb - mid;
    //因为每次扩展x相当于扩展rb, rb最多扩展n次, 所以O(N);
    for(int i = 1; i <= len; i++) {
        int x;
        if(rb < i) x = 1;
        else x = min(p[2*mid - i], rb - i);
        
        while(s2[i+x] == s2[i-x]) x++;
        
        if(i > rb) mid = i, rb = i+x;
        p[i] = x;
    }
}

ans = max(p[]) - 1; 
//原串回文串长度等于新串回文半径减一.