LeetCode 算法题 5. 最长回文子串

分类：algorithm| 发布时间：2016-06-27 00:28:00

题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

解法1

遍历给出的字符串，假设 i 为正在遍历的字符的下标，查出以 i 为中心的回文长度，需要注意长度为奇数和偶数的情况。记录下最长的回文长度和起始下标。

class Solution {
public:
    string longestPalindrome(string s) {
        int longestBeg = 0, longestLen = 0;
        int curBeg = 0, curLen = 0;
        const int size = s.size();
        for (int i = 0; i != size; ++i) {
            if (longestLen > 2 * (size - i) + 1) {
                break;
            }

            getPalindrome(s, size, i, curBeg, curLen);
            if (curLen > longestLen) {
                longestBeg = curBeg;
                longestLen = curLen;
            }
        }

        return string(s, longestBeg, longestLen);
    }

private:
    void getPalindrome(const string &s, int size, int off, int &beg, int &len) {
        if (!off) {
            beg = 0;
            len = 1;
            return;
        }

        int oddbeg, oddlen;
        int evenbeg, evenlen;
        oddPalindrome(s, size, off, oddbeg, oddlen);
        evenPalindrome(s, size, off, evenbeg, evenlen);
        if (oddlen > evenlen) {
            beg = oddbeg;
            len = oddlen;
        } else {
            beg = evenbeg;
            len = evenlen;
        }
    }

    void oddPalindrome(const string &s, int size, int off, int &beg, int &len) {
        beg = off - 1;
        int end = off + 1;
        while (s[beg] == s[end]) {
            if (beg == 0 || end == size - 1) {
                break;
            }

            --beg;
            ++end;
        }

        if (s[beg] != s[end]) {
            ++beg;
            --end;
        }

        len = end - beg + 1;
    }

    void evenPalindrome(const string &s, int size, int off, int &beg, int &len) {
        beg = off - 1;
        int end = off;
        while (s[beg] == s[end]) {
            if (beg == 0 || end == size - 1) {
                break;
            }

            --beg;
            ++end;
        }

        if (s[beg] != s[end]) {
            ++beg;
            --end;
        }

        len = end - beg + 1;
    }
};

解法2（Manacher's algorithm）

算法原理：

如上的算法，算回文长度时需要考虑长度为奇数以及偶数的情况。在 Manacher's algorithm 中，通过在原字符串插入未出现过的字符串的方式，巧妙地将所有回文都变成奇数长度。

比如，插入的字符为 #

s     1     2     2     1     2     3     2     1
S  #  1  #  2  #  2  #  1  #  2  #  3  #  2  #  1  #

然后用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度（包括S[i]，也就是把该回文串“对折”以后的长度），比如S和P的对应关系：

S  #  1  #  2  #  2  #  1  #  2  #  3  #  2  #  1  #
P  1  2  1  2  5  2  1  4  1  2  1  6  1  2  1  2  1
(p.s. 可以看出，P[i]-1正好是原字符串中回文串的总长度）

那么怎么计算P[i]呢？该算法增加两个辅助变量 id和mx，其中 id 为已知的 {右边界最大} 的回文子串的中心， mx 则为 id+P[id]，也就是这个子串的右边界。

然后可以得到一个这么一个结论：如果mx > i，那么P[i] >= MIN(P[2 * id - i], mx - i)。也可以写成：

//记j = 2 * id - i，也就是说 j 是 i 关于 id 的对称点(j = id + (id - i))
if (mx - i > P[j])
    P[i] = P[j];
else /* P[j] >= mx - i */
    P[i] = mx - i; // P[i] >= mx - i，取最小值，之后再匹配更新。

当然光看代码还是不够清晰，还是借助图来理解比较容易。

当 mx - i > P[j] 的时候，以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中，由于 i 和 j 对称，以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中，所以必有 P[i] = P[j]，见下图。

当 P[j] >= mx - i 的时候，以 S[j] 为中心的回文子串不一定完全包含于以 S[id] 为中心的回文子串中，但是基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以 S[i] 为中心的回文子串，其向右至少会扩张到 mx 的位置，也就是说 P[i] >= mx - i。至于 mx 之后的部分是否对称，就只能老老实实去匹配了。

对于 mx <= i 的情况，无法对 P[i]做更多的假设，只能P[i] = 1，然后再去匹配了。

//输入，并处理得到字符串s
int p[1000], mx = 0, id = 0;
memset(p, 0, sizeof(p));
for (i = 1; s[i] != '\0'; i++) {
    p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
    while (s[i + p[i]] == s[i - p[i]]) p[i]++;
    if (i + p[i] > mx) {
        mx = i + p[i];
        id = i;
    }
}

对于原题，解法如下：

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";
        string S(s.size() * 2 + 2, '#');
        S[0] = '$';
        const int size = S.size();
        for (int i = 2; i < size; i += 2) {
            S[i] = s[(i - 1) / 2];
        }

        int p[size];
        fill(p, p + size, 0);
        int longest = 0, longestIdx = 0;
        int id = 0, mx = 0;
        for (int i = 0; i != size; ++i) {
            int j = 2 * id - i;
            p[i] = mx > i ? min(p[j], mx - i) : 1;
            while (S[i - p[i]] == S[i + p[i]]) {
                ++p[i];
            }

            if (longest < p[i]) {
                longest = p[i];
                longestIdx = i;
            }

            if (i + p[i] > mx) {
                id = i;
                mx = i + p[i];
                if (mx >= size) {
                    break;
                }
            }
        }

        int longestBeg = longestIdx - longest + 1;
        int longestLen = 2 * (longest - 1) + 1;
        string retTmp(S, longestBeg, longestLen), ret;
        int retSize = retTmp.size();
        for (int i = 1; i < retSize; i += 2 ) {
            ret.push_back(retTmp[i]);
        }

        return ret;
    }
};

凌云的博客

行胜于言

LeetCode 算法题 5. 最长回文子串

题目

解法1

解法2（Manacher's algorithm）