Manacher

update: 2023/6/7 重画图片（全部由 Krita + 鼠标 完成）

求一个字符串最长的回文子串。 字面意思，回文就是一个串正着读倒着读一样，子串就是一个连续的子序列。

预处理

不难发现对于一个回文字串，有两种情况：

1. \(\texttt{ABBA}\) 即长度为偶数，没有中心字符，半径为 \(2\)，长度为 \(4\)
2. \(\texttt{ABCBA}\) 即长度为奇数，有中心字符，半径为 \(3\)，长度为 \(5\)

懒得给他们处理两种情况，怎么办？只需要插入一些其他字符即可。
比如说我们可以在头部插入一个 \(\texttt?\) 代表串开始，\(\texttt^\) 代表串结束，然后在新串的每一个字符之间插入一个 \(\texttt#\) 号，得到的新串就能达到简化情况的目的。
按照上面的方法处理之后，原来的两个串会变为：
（只观察回文子串）

1. \(\texttt{?#A#B#B#A#^}\) 长度变为奇数，有中心字符，半径为 \(5\)，长度为 \(9\)
2. \(\texttt{?#A#B#C#B#A#^}\) 长度为奇数不变，有中心字符，半径为 \(6\)，长度为 \(11\)

情况被简化成一种，即长度为奇数。与此同时我们发现，新串的回文子串的 半径 \(-1\) 就是原串回文子串的 长度

与此同时，问题不变，还是求串的最长回文子串。

1
2
3
4
5
6
7
8
9
10

void init(std::string& b) {
    b += '$';
    b += '#';
    for (int i = 0; i < n; ++i) {
        b += a[i];
        b += '#';
    }
    b += '^';
    n = b.size();
}

Manacher

基本思想

抽象来说就是对于字符串的每一个位置，维护以这个位置为中心的最长回文串长度同时算出这个回文串的右边界，再通过这个右边界来更新下一个位置的最长回文串长度与右边界。

具体来说，对于一个字符串 \(S\)，开一个数组 \(P_i\) 记录以 \(i\) 为中心的最长回文串半径（含 \(S_i\)），变量 \(mid\) 为在 \(i\) 之前边界最靠右的回文子串的中心，\(mr\)（也就是 \(maxright\)）记录这个回文子串的右边界，通过这些更新下一个位置的这些值。

为了方便说明，以 \(i\) 为中心的最长回文子串称为 \(T_i\)

继承对称点的数据

当前状态：

枚举到 \(i\) 后，对于 \(mr\) 和 \(i\) 来说有两种情况：\(i\) 在 \(mr\) 内或在 \(mr\) 外

• \(i\) 在左侧 即 \(i\) 被 \(T_{mid}\) 包含。
  显然 \(i\) 之前的 \(P_k, k < i\) 都是已知的，\(i\) 在 \(mid\) 为中心的回文子串内，那么一定存在 \(j\) 是 \(i\) 关于 \(mid\) 的对称点，想办法从 \(P_j\) 推出 \(P_i\)，则
  

  
  那么 \(P_j\) 已知，对于以 \(j\) 为中心的最长回文子串 \(T_j\) 来说有两种情况
  1. \(T_j\) 被 \(T_{mid}\) 严格包含，由 \(T_{mid}\) 的回文性质可知，此时 \(P_i\) 可以继承 \(P_j\) 的值，剩下的后续再推。
  2. \(T_j\) 未被 \(T_{mid}\) 严格包含
     
     容易发现，两个青色串一定对称（\(T_{mid}\) 的回文性质），又因为 \(T_j\) 的回文性质，得到两个青色串，左青色串和橙色串分别对称。 此时 \(T_i\) 一定被 \(T_{mid}\) 严格包含。因为如果不被严格包含，则 \(P_{mid}\) 的值仍可以增大，如下图
     
     
     图中蓝色块通过 \(T_{mid}\) 串回文的性质已知相等，每个蓝色块均可以通过自身所在回文串推出其外侧橙色块也是相等的。
     显然这种情况不会出现，因为这种情况下 \(P_{mid}\) 是一个假值，而以上递推过程的前提是前面的值保证正确。

• \(i\) 在右侧
  没有可以继承的值则可以直接重新推，不需要过多考虑。

1
2
3
4
5

if (i < mr) {
    p[i] = min(p[(mid << 1) - i], mr - i);
} else {
    p[i] = 1;
}

更新 \(P_i\)

直接从当前记录的半径向外继续枚举，直到遇到两个不相同的字符为止（边界上有 $ ^，枚举到一定会停止，所以不用考虑边界问题）。

1
2
3

while (b[i - p[i]] == b[i + p[i]]) {
    ++ p[i];
}

更新 \(mr\) 和 \(mid\)

前文说过 \(mr\) \(mid\) 都是边界最靠右的回文子串的属性，那么只需要判断新找到的回文子串右边界是否大于 \(mr\) 即可。

1
2
3
4

if (i + p[i] > mr) {
    mr = i + p[i];
    mid = i;
}

至此 Manacher 算法主要过程结束。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

void init(std::string& b) {
    b += '$';
    b += '#';
    for (int i = 0; i < n; ++i) {
        b += a[i];
        b += '#';
    }
    b += '^';
    n = b.size();
}

void manacher() {
    int mr = 0, mid;
    for (int i = 1; i < n; ++i) {
        if (i < mr) {
            p[i] = min(p[(mid << 1) - i], mr - i);
        } else {
            p[i] = 1;
        }

        while (b[i - p[i]] == b[i + p[i]]) {
            ++p[i];
        }

        if (i + p[i] > mr) {
            mr = i + p[i];
            mid = i;
        }
    }
}

时间复杂度¹

当 \(P_j\) 左侧取到左边界及以外时，\(P_i\) 才需要更新（其他情况都因为不满足条件而不用进循环），而右端点是单调递增且严格小于等于 \(n\) 的，因此总时间复杂度为 \(\operatorname{O}(n)\)