Longest Palindromic Substring

描述

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

分析

最长回文子串，非常经典的题。

思路一：暴力枚举，以每个元素为中间元素，同时从左右出发，复杂度O(n^2)。

思路二：记忆化搜索，复杂度O(n^2)。设f[i][j] 表示[i,j]之间的最长回文子串，递推方程如下：

  1. f[i][j] = if (i == j) S[i]
  2.           if (S[i] == S[j] && f[i+1][j-1] == S[i+1][j-1]) S[i][j]
  3.           else max(f[i+1][j-1], f[i][j-1], f[i+1][j])

思路三：动规，复杂度O(n^2)。设状态为f(i,j)，表示区间[i,j]是否为回文串，则状态转移方程为

f(i,j)={true,i=jS[i]=S[j],j=i+1S[i]=S[j] and f(i+1,j−1),j>i+1f(i,j)=\begin{cases}true & ,i=j\S[i]=S[j] & , j = i + 1 \S[i]=S[j] \text{ and } f(i+1, j-1) & , j > i + 1\end{cases}

思路四：Manacher’s Algorithm, 复杂度O(n)。详细解释见 http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html。

备忘录法

  1. // Longest Palindromic Substring
  2. // 备忘录法，会超时
  3. // 时间复杂度O(n^2)，空间复杂度O(n^2)
  4. namespace std {
  5. template<>
  6. struct hash<pair<int, int>> {
  7.     size_t operator()(pair<int, int> const& p) const {
  8.         return p.first * 31 + p.second;
  9.     }
  10. };
  11. }
  13. class Solution {
  14. public:
  15.     string longestPalindrome(string const& s) {
  16.         cache.clear();
  17.         return cachedLongestPalindrome(s, 0, s.length() - 1);
  18.     }
  20. private:
  21.     unordered_map<pair<int, int>, string> cache;
  23.     string longestPalindrome(string const& s, int i, int j) {
  24.         const int length = j - i + 1;
  25.         if (length < 2) return s.substr(i, length);
  27.         const string& s1 = cachedLongestPalindrome(s, i + 1, j - 1);
  29.         if (s1.length() == length - 2 && s[i + 1] == s[j - 1])
  30.             return s.substr(i, length);
  32.         const string& s2 = cachedLongestPalindrome(s, i + 1, j);
  33.         const string& s3 = cachedLongestPalindrome(s, i, j - 1);
  35.         // return max(s1, s2, s3)
  36.         if (s1.length() > s2.length()) return s1.length() > s3.length() ? s1 : s3;
  37.         else return s2.length() > s3.length() ? s2 : s3;
  38.     }
  40.     string cachedLongestPalindrome(string const& s, int i, int j) {
  41.         auto key = make_pair(i, j);
  42.         auto pos = cache.find(key);
  44.         if (pos != cache.end()) return pos->second;
  45.         else return cache[key] = longestPalindrome(s, i, j);
  46.     }
  47. };

动规

  1. // Longest Palindromic Substring
  2. // 动规，时间复杂度O(n^2)，空间复杂度O(n^2)
  3. class Solution {
  4. public:
  5.     string longestPalindrome(const string& s) {
  6.         const int n = s.size();
  7.         bool f[n][n];
  8.         fill_n(&f[0][0], n * n, false);
  9.         // 用 vector 会超时
  10.         //vector > f(n, vector(n, false));
  11.         size_t max_len = 1, start = 0;  // 最长回文子串的长度，起点
  13.         for (size_t i = 0; i < s.size(); i++) {
  14.             f[i][i] = true;
  15.             for (size_t j = 0; j < i; j++) {  // [j, i]
  16.                 f[j][i] = (s[j] == s[i] && (i - j < 2 || f[j + 1][i - 1]));
  17.                 if (f[j][i] && max_len < (i - j + 1)) {
  18.                     max_len = i - j + 1;
  19.                     start = j;
  20.                 }
  21.             }
  22.         }
  23.         return s.substr(start, max_len);
  24.     }
  25. };

Manacher’s Algorithm

  1. // Longest Palindromic Substring
  2. // Manacher’s Algorithm
  3. // 时间复杂度O(n)，空间复杂度O(n)
  4. class Solution {
  5. public:
  6.     // Transform S into T.
  7.     // For example, S = "abba", T = "^#a#b#b#a#$".
  8.     // ^ and $ signs are sentinels appended to each end to avoid bounds checking
  9.     string preProcess(const string& s) {
  10.         int n = s.length();
  11.         if (n == 0) return "^$";
  13.         string ret = "^";
  14.         for (int i = 0; i < n; i++) ret += "#" + s.substr(i, 1);
  16.         ret += "#$";
  17.         return ret;
  18.     }
  20.     string longestPalindrome(string s) {
  21.         string T = preProcess(s);
  22.         const int n = T.length();
  23.         // 以T[i]为中心，向左/右扩张的长度，不包含T[i]自己，
  24.         // 因此 P[i]是源字符串中回文串的长度
  25.         int P[n];
  26.         int C = 0, R = 0;
  28.         for (int i = 1; i < n - 1; i++) {
  29.             int i_mirror = 2 * C - i; // equals to i' = C - (i-C)
  31.             P[i] = (R > i) ? min(R - i, P[i_mirror]) : 0;
  33.             // Attempt to expand palindrome centered at i
  34.             while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
  35.                 P[i]++;
  37.             // If palindrome centered at i expand past R,
  38.             // adjust center based on expanded palindrome.
  39.             if (i + P[i] > R) {
  40.                 C = i;
  41.                 R = i + P[i];
  42.             }
  43.         }
  45.         // Find the maximum element in P.
  46.         int max_len = 0;
  47.         int center_index = 0;
  48.         for (int i = 1; i < n - 1; i++) {
  49.             if (P[i] > max_len) {
  50.                 max_len = P[i];
  51.                 center_index = i;
  52.             }
  53.         }
  55.         return s.substr((center_index - 1 - max_len) / 2, max_len);
  56.     }
  57. };

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/string/longest-palindromic-substring.html