求出所有的回文，从中找出最长。两种做法。首先是DP，用DP[i][j]表示s[i, j]是否为回文。我们有递推公式：
- DP[i][j] = true, if (DP[i + 1][j - 1] == true || j - i > 2) && s[i] == s[j]
- otherwise, DP[i][j] = false
时间复杂度空间复杂度都为O(n^2)，代码如下：
第二种就是从每一个字符开始向两边展开，直到不是回文为止。常数空间，时间复杂度worst case O(n^2)，但是我们有剪枝，所以正常情况是比它快的。代码如下：
最后我们介绍一个线性时间求最长回文子串的算法，manacher算法。对于string s我们首先做预处理，将其每一个字符中间插入一个特殊字符，比如#。例如s为aacaa的情况，预处理之后就变为#a#a#c#a#a#，处理完之后有一个好处，就是在原字符串中长度为奇数和偶数回文串，在新字符串中长度都为奇数。比如aa变为#a#a#，aacaa变为#a#a#c#a#a#。如此一来，我们只需要在新字符串中找到奇数长度最长回文串即可。为了在线性时间找到最长的奇数长度的回文串，我们用r[i]记录以i位置为中心的回文的最长半径，最小为1。此外，我们用maxRight和maxPos记录已经扫过的i中，以maxPos为中心的回文是向右延伸到最远的，一直到maxRight。那么我们有几种情况，第一种是当前我们所在位置i < maxRight，如图所示：
那么我们可以找到i关于maxPos的对称点j = 2* maxPos - i，因为i永远是在maxPos右边的，所以对称点一定在i的左边。由于j的信息我们是已经知道了的。假设r[j] = k，有以下两种情况：
- k < maxRight - maxPos + 1，那么由于i和j是在以maxPos为中心的回文中完全对称的，所以以i为中心的回文的半径，不可能超过k，因为i + k + 1和i - k - 1处的字符左右不match，j + k + 1和j - k - 1的结论的镜像。
- k >= maxRight - maxPos + 1, i处最长回文的右端点已经到达maxRight，其还能够多长我们也不知道，因为没有足够的信息，所以我们继续match。j的结论最多只作用到maxRight，因为超过maxRight之后，对称性消失了，我们只能一个一个match来确认最长的。
假设i >= maxRight，我们没有足够的信息，初始r[i]为1，一个一个匹配。代码如下：
时间复杂度就等于maxRight的向右移动的速度，因为处于maxRight左边的所有字符我们只会匹配一次，如果右边的字符被匹配了，maxRight就会向右扩张。很明显这个是线性的。
No comments:
Post a Comment