最长回文子串 Manacher 算法

ACM学习笔记
目录
  1. 1. 算法简介
  2. 2. 算法原理
  3. 3. 算法实现
  4. 4. 复杂度分析
  5. 5. Hint
  6. 6. 小记

算法简介

Manacher 算法能够在线性时间内求出一个字符串的最长回文子串。

算法原理

记原字符串为 S，长度为 N。
在 S 中的任一对相邻字符间插入一个特殊字符**’$’**，目的是保证新串中所有的回文子串长度都为奇数。
设以 s[i] 为中心的最长回文串长度为 $2R[i]+1$。
那么，如果 $j < i$ 且 $j+R[j] > i$；作 $i$ 点关于 $j$ 的对称点 $i’$，则必有 $i’ > j-R[j]$。

见下图

在上图中，$i’-R[i’] > j-R[j’]$；由对称性，可以断言 $R[i]=R[i’]$。

事实上，假设 $k’=i’-R[i’]-1$ 关于 $j$ 的对称点为 $k$; $k$ 关于 $i$ 的对称点为 $k_i$；$k_i$ 关于 $j$ 的对称点为 $k’_i$ 。

由于 $S[k]=S[k’]$，$S[k_i]=S[k’_i]$；$S[k’] \neq S[k’_i]$。
所以 $S[k] \neq S[k_i]$，故 $R[i]=R[i’]$。

在上图中，$i’-R[i’] < j-R[j’]$；由对称性，可以断言 $R[i]=j+R[j]-i$。

当 $j+R[j] \leqslant i$ 时，不能做出更多的假设，只能暴力匹配。
幸运地是，可以证明暴力匹配的总字符数是 $O(N)$ 的。

算法实现

所谓的插入特殊字符是为了方便讲解，实现时可以将回文串 $[l,r]$ 的长度存在 $R[l+r]$ 中。
不难发现，当回文串长度为偶数时，$l+r \equiv 1\mod(2)$。

参考了《ACM国际大学生程序设计竞赛:算法与实现》的代码。

1
2
3
4
5
6
7
8
9
10
11
12
void Manacher(char* S, int* R, int n) {
    R[0] = 1;
    int dn = (n<<1)-1;
    for(int i=1, j=0; i < dn; ++i) {
        int l = i>>1, r = i-l;
        int rst = (j-1>>1)+R[j];
        R[i] = rst < r? 0: min(rst-r+1, len[(j<<1)-i]);
        for(; l-R[i] >=0 && r+R[i] < n && S[l-R[i]] == S[r+R[i]]; ) ++R[i];
        if( r+R[i] > rst ) j = i;
    }
}

复杂度分析

由于每一次只从未被匹配过的字符出发往右扩展，一共只有 $O(N)$ 个字符，所以复杂度是线性的。

  • 空间复杂度 $O(N)$
  • 时间复杂度 $O(N)$

Hint

1
2
if( i&1 ) len = R[i]*2;
else len = R[i]*2-1;

小记

第一次接触这个算法是在 2016 年武大的校赛上；
第一次没有抱大腿获奖;
虽然奖品有点坑。。。