跳转至

Manacher

对于一个字符串 \(s\)，如果 \(s=rev(s)\)，则称 \(s\) 为回文串。对于 \(|s|\bmod 2=1\)，称下标 \(\lfloor\frac{|s|}{2}\rfloor\) 为 \(s\) 的回文中心。

当 \(|s|\bmod 2=0\) 时，\(s\) 没有回文中心。为了避免这种情况，我们将原串中相邻两个字符之间都插入一个特殊字符 $（%，# 等）。这样原串的所有回文子串就都有确定的回文中心了。

aabaabaa \(\rightarrow\) $a$a$b$a$a$b$a$a$

对于字符串 \(s\)，定义 \(z[i]\) 表示 \(s\) 中以 \(i\) 为回文中心，极长的回文子串的回文半径。

Manacher（马拉车）算法可以在 \(O(n)\) 的时间内求出 \(z[i]\)。其线性的时间复杂度依赖于 \(\max_{j\le i}\{j+z[j]\}\) 的增量为 \(O(n)\) 级别。

考虑从左往右遍历字符串的每一个字符，设当前枚举到第 \(i\) 个字符，\(j+z[j]\) 在 \(j=k\le i-1\) 处取到最大值。考虑 \(i\) 关于 \(k\) 对称的位置 \(p=2k-i\)，Manacher 的核心思想就是从 \(p\) 转移到 \(i\)。分讨几种情况：

\(\large case\ 1\)

\[ i> k+z[k] \]

直接暴力扩展即可，这会增大 \(\max_{j\le i}\{j+z[j]\}\)，均摊正确。

\(\large case\ 2\)

\[ p-z[p]<k-z[k] \]

由于 \(s\big[k-z[k]-1\big]\ne s\big[k+z[k]+1\big]\)，因此 \(z[i]\) 将被限制为 \(k+z[k]-i\)；

\(\large case\ 3\)

\[ p-z[p]>k-z[k] \]

显然 \(z[i]=z[p]\)；

\(\large case\ 4\)

\[ p-z[p]=k-z[k] \]

由于式子中存在两个不等号，因此我们无法判断 \(z[i]\) 能否在 \(z[p]\) 的基础上继续扩展。然而此时 \(i+z[i]\ge k+z[k]\)，直接暴力扩展将会增大 \(\max_{j\le i}\{j+z[j]\}\)，均摊正确。

代码中，我们一般将 \(case\ 2,3,4\) 合并考虑。

模板代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
void manacher() {
    s.push_back('$');
    for(int i = 0; i < s1.size(); i++) {
        s.push_back(s1[i]);
        s.push_back('$');
    }
    n = s.size();
    int k = 0;
    for(int i = 1; i < n; i++) {
        if(i > k + z[k]) {
            while(i + z[i] < n && i >= z[i] && s[i + z[i]] == s[i - z[i]]) ++z[i];
            --z[i];
            k = i;
        } else {
            z[i] = min(z[2 * k - i], k + z[k] - i);
            while(i + z[i] < n && i >= z[i] && s[i + z[i]] == s[i - z[i]]) ++z[i];
            --z[i];
            if(i + z[i] > k + z[k]) k = i;
        }
    }
}