本文共 1667 字，大约阅读时间需要 5 分钟。

这个题目出现在华为的面试题目上了。开始看这个题目的时候感觉好难，根本无从下手。说实话，我连N3次方的算法都没想出来，（当然也没去想那么笨的算法，当然历史不容假设，可能我真的连笨的方法也想不出来）。

在leetcode上有人对这个题目发了两篇文章，

第一篇文章 第一篇文章讲了如何用动态规划算法用N2次方的时间复杂度和空间复杂度做出来。还讲了一个利用N2次方时间复杂度，常量空间复杂度做出来的算法。都具有启发意义

重点在第二篇文章里面。这里讲了一个线性时间复杂度的算法。

具体的算法如下

// Transform S into T.// For example, S = "abba", T = "^#a#b#b#a#$".// ^ and $ signs are sentinels appended to each end to avoid bounds checkingstring preProcess(string s) {  int n = s.length();  if (n == 0) return "^$";  string ret = "^";  for (int i = 0; i < n; i++)    ret += "#" + s.substr(i, 1);  ret += "#$";  return ret;}string longestPalindrome(string s) {  string T = preProcess(s);  int n = T.length();  int *P = new int[n];  int C = 0, R = 0;  for (int i = 1; i < n-1; i++) {    int i_mirror = 2*C-i; // equals to i' = C - (i-C)    P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;    // Attempt to expand palindrome centered at i    while (T[i + 1 + P[i]] == T[i - 1 - P[i]])      P[i]++;    // If palindrome centered at i expand past R,    // adjust center based on expanded palindrome.    if (i + P[i] > R) {      C = i;      R = i + P[i];    }  }  // Find the maximum element in P.  int maxLen = 0;  int centerIndex = 0;  for (int i = 1; i < n-1; i++) {    if (P[i] > maxLen) {      maxLen = P[i];      centerIndex = i;    }  }  delete[] P;  return s.substr((centerIndex - 1 - maxLen)/2, maxLen);}

看了讲解都很好理解。但是有一个地方就是这段代码

P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;

为啥要对(R-i, P[i_mirror])取小的呢？我思考出来结果是这样的。 在当前的中心中，我们所做的一切推断都要以当前中心为中心，也就是所有的操作右边不能超过R。这就是判断R>i的意义。那么如果在操作范围内，如果i的对称点的范围小于R-i，我们可以确定P[i]=P[i_mirror]。

那么可能R-i要小于P[i_mirror]吗？这个是可能的。因为P[i_mirror]计算的时候并不是以当前中心为中心的，他是以另一个点为中心，这个时候，就要比较R-i, P[i_mirror]取最小了。

转载地址：http://yduvb.baihongyu.com/