Leetcode 5 - Longest Palindromic Substring(Manacher or Dp)

问题描述

求一个字符串的最长回文子串

思路

算法1

dp，时间复杂度 O(n2)

算法描述

最先考虑的状态表示是： d[i,j] ，字符串区间 [i,j] 的最长回文子串。但是因为要记录前驱节点不是很好写。所以我们的状态表示需要改进。 状态表示： d[i,j] ，区间 [i,j] 是否为回文串。 转移方程： d[i,j]=(s[i]==s[j]∧(j−i<3∨d[i+1],j−1])) 注意： 1. 边界情况，当字符串长度小于等于3的时候，我们不用转移到 d[i+1,j−1] 。 2. 注意循环的顺序。

代码

const int maxn = 1005; class Solution { public: string longestPalindrome(string s) { int d[maxn][maxn], n = s.length(); string res = ""; for (int i = n - 1; i >= 0; i--) { for (int j = i; j < n; j++) { d[i][j] = (s[i] == s[j] && (j - i < 3 || d[i + 1][j - 1])); if (d[i][j] && (j - i + 1 > res.length())) res = s.substr(i, j - i + 1); } } return res; } };

算法2

Manacher算法（传说中的马拉车算法= =），时间复杂度 O(n) 。

算法描述

预处理

其思想就是基于前面已经匹配过的部分。 首先，我们通过在字符串之间加上’#’来将所有长度为偶数的字符串转成长度为奇数的字符串，长度为奇数的字符串仍然为奇数长度。 比如： 123 => #1#2#3#, 1234 => #1#2#3#4# 并且，我们在最开头的部分加上一个’$’来标记开头。 比如我们将1234322转成：$#1#2#3#4#3#2#2#

匹配

我们用一个p[]来表示： pi 代表当前第i个元素能向左或者向右延伸的最大长度。比如上面例子的p[8] = 6(数4的位置，并且包括自身)。 其实我们的问题关键就是求出p[]数组。

假设我们当前0到j之间的部分已经匹配，那么，对于j，我们已知的部分即为 j+pj 。既然我们要利用已知的部分去推断我们剩下的j + 1及其之后，那么，我们就需要已知部分知道的越多越好。所以，我们需要保存能够扩展到的最后一位。

所以，我们用mx表示已知的最远的一位（并不是回文串的长度最大，而是其对应的中心+扩展长度最大），id为其对应的中心。那么， mx=id+pid 。 现在，对于我们新的一位i，先给出 pi 的值： pi≥min(p2⋅id−i,mx−i)(p2⋅id−i 为i关于id的对称点，我们令为j)。 分为如下两种情况来讨论： 情况1： pj≥mx−i j和i对称，这时候，看图和容易明白p[i]本来可以等于p[j]，但是因为此时mx之后部分未知，所以我们只能截取到mx位置上。所以 pi=mx−i 。 情况2： pj<mx−i 根据图片，此时我们 pi=pj 。

所以，我们的manacher的核心代码就为：

p[i] = i >= mx ? 1 : min(p[2 * id - i], mx - i)

最后，我们还需要对于之后的未知部分继续扩展。

代码

class Solution { public: char* preInit(string s) { char *a = new char[s.length() * 2 + 2]; a[0] = '$'; int i = 1, j = 0; while (j < s.length()) { a[i++] = '#'; a[i++] = s[j++]; } a[i++] = '#'; return a; } string longestPalindrome(string s) { //----------------------------- char *a = preInit(s); int n = s.length() * 2 + 2; vector<int> p(n, 0); int id = 0, mx = 0; for (int i = 1; i < n; i++) { p[i] = (i >= mx ? 1 : min(p[2 * id - i], mx - i)); while (i - p[i] >= 0 && i + p[i] < n && a[i - p[i]] == a[i + p[i]]) p[i]++; if (i + p[i] > mx) { id = i; mx = i + p[i]; } } //----------------------------- int ind = 0, maxL = 0; for (int i = 0; i < n; i++) { if (p[i] > maxL) { ind = i; maxL = p[i]; } } string res = ""; for (int i = ind - p[ind] + 1; i < min(n, ind + p[ind]); i++) if (a[i] != '#') res.push_back(a[i]); delete a; return res; } };