解题报告之最长回文子串

题目很简单，就是求解一个字符串中最长的回文子串，回文字符串是指颠倒之后的字符串和原来的字符串完全一样。网上很多人的博文，像 kangroger,还有把最牛b的 Manacher 算法说得很清晰的 pi9nc和 yzl_rex，介绍了四种解法：分别是暴力法（$O(n^3)$），动态规划（$O(n^2)$），中心扩展（$O(n^2)$）和Manache法（$O(n)$）。本博文只是对这四种方法的自我实现。

题目

题目来自 HiHoCoder 上第一周的题目最长回文子串，题目大意是：

给定一个字符串，求解这个字符串中最长的回文子串。而回文字符串是指颠倒之后的字符串和原来的字符串完全一样。

思路

暴力求解
暴力求解的方法分两步，第一步是得到字符串所有的子串（$n\times(n+1)/2$个），第二步是判断每一个子串是否是回文子串（$n/2$ 比较操作），如果是则记录下长度，不是则舍弃。所以暴力求解方法的时间复杂度为 $O(n^3)$。
动态优化
这里的动态优化说白了就是一种空间换时间的解法。其具体的做法就是在一个二维数组 dp 中记录下i到j是否是回文，即 dp[i][j]=1/0,那么要判断 dp[m][n] 是否是回文就得看 dp[m-1][n-1] = 1 && buf[m] = [n]。由于要填充这样 $n^2$ 的二维数组，所以动态优化解法的时间复杂度 $O(n^2)$。
中心扩展
中心扩展的思路很简单，就是以字符串中某个字符为中心，然后向两边对称扩展，判断最边缘字符是否相等，以此来统计回文子串的长度。不过这里面要注意回文子串的长度可能为偶数，也就是说它以两个字符的中间为对称中心。所以要分两种情况考虑，总的来说，中心扩展方法的时间复杂度为 $O(n^2)$。
Manacher算法
你猜测的没，该算法就是这个叫 Manacher 的人想出的算法，用于解决最长回文子串问题，其时间复杂度能达到 $O(n)$。该算法的核心思想是充分利用回文字符串的对称性，即利用前面已经算得的对称半径减少或直接求取当前要求的对称半径。下个部分将详细解释该算法。

算法说明

这里主要说明动态规划算法和 Manacher 算法。重点在 Mancher 算法，而动态规划算法只是提一下其中二维数组的动态申请。

动态规划算法

二维数组的动态申请用 c 实现的步骤：
1. 申请一个长度为 len 的指针数组 (int **)dp，用来存放二维数组每行的首地址。
2. 给 dp[0] 申请一个 $len*len$ 的数组，用于存放具体数据。
3. 给 dp[i] 赋上二维数组每行首地址。
4. $\cdots$
5. 释放数组 dp[0]
6. 释放指针数组 dp

代码演示

1// 动态申请二位数组并初始化
2int **dp = (int **)malloc(sizeof(int *) * len);
3dp[0] = (int *)malloc(sizeof(int) * len * len);
4for(i=1; i<len; i++)
5    dp[i] = dp[i-1] + len;
6
7// 释放申请的二位数组
8free(dp[0]);
9free(dp);

Mancher算法

假设
为解释清楚 Manacher 算法，作如下假定：
- 所有的回文子串的数目都是奇数（通过向字符首尾和字符间插入特殊字符集’#‘实现）
- 辅助数组 radius 用来存储对称半径。即 radius[i] 表示以第 i 个字符为中心构成的回文子串的半径。像字符串 “#a#” 的回文半径为1。
符号说明
如下图所示，我们要根据回文字符串 buf 和 $radius[0]～radius[i-1]$ 来求取 radius[i]。

图中符号说明如下：
- id 表示以前 i 个字符中第 id 个字符为中心构成的回文子串最右边字符的索引值最大，即 $id = argmax(radius[k]+k),k<i$。易知 $ id<i $。
- mx 表示以第 id 个字符为中心构成的回文子串最右边字符的索引值，即 $mx = radius[id]+id, id<i $。
- j 是 i 关于id的对称点，即 $ j = 2 * id - i $。
分情况讨论
1. $ mx < i$
  此时radius的前i个值不起任何作用，就像初始时根据$radius[0]=0$求解$radius[1]$，此时$id=0,mx=0$。
```
1if(mx<i){
2    k=1;
3    // 以i为中心，回文子串的半径
4    while(newbuf[i-k]==newbuf[i+k]&&i-k>=0&&i+k<len)
5        k++;
6    radius[i]=k-1;
7}
```
2. $ mx > i $
  1. $ mx-i >= radius[j] $
    $mx-i$ 代表 i 到 mx 的距离，而 $radius[j]$ 就是图中绿线的一半距离。如果 $mx-i > radius[j]$ 说明 $radius[i]=radius[j]$，因为 $[2*id-mx,mx]$ 是关于 id 对称的，而 i 和 j 也是关于 id 对称的。
```
1if(mx-i >= radius[j])
2    radius[i]=radius[j];
```
  2. $ mx-i < radius[j]$
    此时我们根据对称性，能够获得 $radius[i]>=radius[j]$ 的。所以我们直接从 mx+1 开始判断 $buf[mx+t]==buf[2*i-mx-t],t=1,2,\cdots$ 。
```
1if(mx-i<radius[j]){
2    k=mx-i+1;
3    // 以i为中心，回文子串的半径从mx-i+1开始验证
4    while(newbuf[i-k]==newbuf[i+k]&&i-k>=0&&i+k<len)
5        k++;
6    radius[i]=k-1;
7}
```

情况融合
仔细思考一下，发现第二种情况里面的两种情况可以融合，说白点就是取图中 i 到 mx 的距离和图中一半绿线距离中的最小值，即 $radius[i]=min(radius[j],mx-i)$。然后再进行向外扩展，看 $radius[i]$ 能否更大。

 1radius[0]=0;
 2for(i=1; i<len; i++){
 3    if(mx>i){
 4        if(radius[j]<mx-i)
 5            radius[i]=radius[j];
 6        else
 7            radius[i]=mx-i;
 8    }else{
 9        radius[i]=1;
10    }
11    for(;newbuf[i+radius[i]]==newbuf[i-radius[i]]&&i+radius[i]<len&&i-radius[i]>=0;radius[i]++);
12    // 更新id，mx
13    if(radius[i]+i>mx){
14        id=i;
15        mx=radius[i]+i;
16    }
17}

完整代码

举一反三

无

也可以看看

题目

思路

算法说明

动态规划算法

Mancher算法

举一反三