Algorithm LongestPalindromic SubString

Description

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"

Output: "bb"

Submission

class Solution {
    public String longestPalindrome(String s) {
            if (s.length() <= 1) {
      return s;
    }
    StringBuffer stringBuffer = new StringBuffer();

    for (int i = 0; i < s.length(); ++i) {
      stringBuffer.append("#");
      stringBuffer.append(s.charAt(i));
    }
    stringBuffer.append("#");

    int length = stringBuffer.length();

    int[] posVal = new int[length];

    int maxLength = 0;
    int rMax = 0;
    int maxCenter = -1;
    int validPos = -1;

    for (int i = 0; i < length; ++i) {
      if (i == 0) {
        posVal[i] = 0;
        maxCenter = i;
        rMax = 0;
        validPos = 0;
      } else {
        int left;
        int right;
        if (rMax > i) {
          int opPos = 2 * maxCenter - i;
          int leastLen = posVal[opPos];
          leastLen = Math.min(leastLen, rMax - i);
          left = i - leastLen;
          right = i + leastLen;
          while(left >= 0 && right < length && stringBuffer.charAt(left) == stringBuffer.charAt(right)) {
            left --;
            right ++;
          }

        } else {
          left = i - 1;
          right = i + 1;
          while(left >= 0 && right < length && stringBuffer.charAt(left) == stringBuffer.charAt(right)) {
            left --;
            right ++;
          }

        }
        if (right - 1 > rMax) {
          rMax = right - 1;
          maxCenter = i;
        }
        posVal[i] = right - 1 - i;

      }


      if (posVal[i] > maxLength) {
        maxLength = posVal[i];
        validPos = i;
      }

    }

    StringBuffer res = new StringBuffer();
    for (int k = validPos - maxLength; k <= validPos + maxLength; ++k) {
      if ((k & 1) == 1) {
        res.append(stringBuffer.charAt(k));
      }
    }
    return res.toString();
    }
}

Solution

获取最长回文子串，上面代码的实现是基于Manacher's algorithm.

在讲解这个算法之前，我们先讲述一个简单的实现方式，只是在时间复杂度上较高达到了O(N²)

针对字符串

"acdeedcb"

我们可以知道最长回文子串是 "cdeedc"

首先我们在字符串的每个字符之间插入一个额外字符 '#'，便形成了"#c#d#e#e#d#c",这个时候我们依次遍历该字符串的每个字符，
从左往右。

当遍历到位置 i时，分别比较left和right对应的字符是否相同，如果相同则继续向两侧扩张比对，直至不同或到边界的地方停止，记录此时仍满足字符相等的位置，因而可以计算出以i为中心的最长回文子串。当整个字符串都被遍历完之后
便可以得到所有位置的最长回文子串，得到最终结果。

Manacher 算法 的思路是基于上面遍历算法的基础之上的，利用已遍历过位置的对称信息，在此基础之上降低了时间复杂度。

我们假设从左至右依次遍历，位置为i，记录访问过的所有位置的回文子串所能到达的最右边界，记为rMax,同时记录该边界对应的中心 maxCenter

那么我们必然能够利用到一点信息，即当前访问的位置 i必然在之前已经标记到的位置 maxCenter 的右侧，这个时候会引入两种情况，

i在rMax的左侧，那么i在(2maxCenter-rMax,rMax)区间内的对称性必然是一致的，也就是说 posVal[i] = Math.min(pos[2maxCenter-i], rMax-i)，其中posVal数组记录每个位置的回文子串右边界至当前位置的距离，也对应着回文子串的长度。

我们能够在i位置直接得到当前位置回文子串的最小长度，以此为边界向两侧扩张，可以得到具体的i位置的回文子串的长度。

Runtime: 10 ms, faster than 79.83% of Java online submissions for Longest Palindromic Substring.

Memory Usage: 39.6 MB, less than 18.89% of Java online submissions for Longest Palindromic Substring.