目录

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; //原串回文串长度等于新串回文半径减一.