https://leetcode-cn.com/problems/longest-palindromic-substring/

暴力解

中心向外扩方法，只能找到奇数长度回文子串，偶数长度回文串没覆盖到 (虚轴)

解决方法：在头尾和每两个字符串中间添加特殊字符 # （把虚轴给补上了）
- 长度除以2就对应原始串的长度

动态规划解法O(N^2)

解法 2: 最长公共子串
根据回文串的定义，正着和反着读一样，那我们是不是把原来的字符串倒置了，然后找最长的公共子串就可以了。例如 S = “caba” ，S = “abac”，最长公共子串是 “aba”，所以原字符串的最长回文串就是 “aba”。

关于求最长公共子串（不是公共子序列），有很多方法，这里用动态规划的方法，
整体思想就是，申请一个二维的数组初始化为 0，然后判断对应的字符是否相等，相等的话

arr [ i ][ j ] = arr [ i - 1 ][ j - 1] + 1 。

当 i = 0 或者 j = 0 的时候单独分析，字符相等的话 arr [ i ][ j ] 就赋为 1 。

arr [ i ][ j ] 保存的就是公共子串的长度。

再看一个例子，S=”abc435cba”，S=”abc534cba”，最长公共子串是 “abc” 和 “cba”，但很明显这两个字符串都不是回文串。

所以我们求出最长公共子串后，并不一定是回文串，我们还需要判断该字符串倒置前的下标和当前的字符串下标是不是匹配。

比如 S=”caba”，S’=”abac” ，S’ 中 aba 的下标是 0 1 2 ，倒置前是 3 2 1，和 S 中 aba 的下标符合，所以 aba 就是我们需要找的。当然我们不需要每个字符都判断，我们只需要判断末尾字符就可以。

首先 i，j 始终指向子串的末尾字符。所以 j 指向的红色的 a 倒置前的下标是 beforeRev = length-1-j=4-1-2=1，对应的是字符串首位的下标，我们还需要加上字符串的长度才是末尾字符的下标，也就是 beforeRev+arr[i][j]-1=1+3-1=3，因为 arr[i][j] 保存的就是当前子串的长度，也就是图中的数字 3。此时再和它与 i 比较，如果相等，则说明它是我们要找的回文串。

之前的 S=”abc435cba”，S’=”abc534cba”，可以看一下图示，为什么不符合。

当前 j 指向的 c，倒置前的下标是 beforeRev=length-1-j=9-1-2=6，对应的末尾下标是beforeRev+arr[i][j]-1=6+3-1=8，而此时 i=2，所以当前的子串不是回文串。

代码的话，在上边的基础上，保存 maxLen 前判断一下下标匹不匹配就可以了。

//动态规划解法: O（N^2）
//将字符串反转，然后求反转后的字符串和原字符串的最长公共子串长度
// 一个样本作行一个样本作列对应模型
public String longestPalindrome1(String s) {
    if (s == null || s.length() == 0) {
        return "";
    }
    String origin = s; //原字符串
    String reverse = new StringBuilder(s).reverse().toString(); //反转后的字符串
    int length = s.length();
    //dp[i][j]: origin中以i结尾 与 reverse中以j结尾 的最长公共子串长度
    int[][] dp = new int[length][length];
    int maxLen = 0; // 记录长度
    int maxEnd = 0; // 记录结尾
    for (int i = 0; i < length; i++) {
        for (int j = 0; j < length; j++) {
            if (origin.charAt(i) == reverse.charAt(j)) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
            }
            if (dp[i][j] > maxLen) {
                //需要判断是否是真的回文串， 因为有可能不是回文串，
                //比如S="abc435cba" S‘="abc534cba"，最长公共子串是 "abc" 和 "cba"，但很明显这两个字符串都不是回文串
                //所以求出最长公共子串后，海需要判断该字符串倒置前的下标和当前的字符串下标是不是匹配
                //j位置的字符倒置前的原坐标
                int beforeRev = length - 1 - j; // 这个就是j位置字符在原字符串中的位置
                // 开始下标 + 长度 - 1
                if (beforeRev + dp[i][j] - 1 == i) { //是回文串
                    maxLen = dp[i][j];
                    maxEnd = i;
                }
            }
        }
    }
    return s.substring(maxEnd - maxLen + 1, maxEnd + 1);
}

时间复杂度：两层循环 O(n²)O(n²)。

空间复杂度：一个二维数组 O(n²)O(n²)。

马拉车算法 O(N)

5.⭐最长回文子串（马拉车算法） - 图3

i在R内
- （ i’）跑到L…R外，i位置的最长回文长度是2rの证明：
- L~L’ 和 R’ ~R关于C点对称又都在大回文区内
  - 1）T == Y
  - 2) X == T
  - 3) X ≠ Z
  - SO 推得 Y ≠ Z
伪代码分析复杂度
- 复杂度的估算绑定到R的变化上

 public String longestPalindrome(String s) {
     if (s == null || s.length() == 0) {
         return "";
     }
     char[] str = manacherString(s);
     int[] pArr = new int[str.length];
     int R = -1;
     int C = -1;
     int max = Integer.MIN_VALUE;
     int mid = 0;
     for (int i = 0; i < str.length; i++) {
         pArr[i] = i < R ? Math.min(pArr[2 * C - i], R - i): 1;
         while (i + pArr[i] < str.length && i - pArr[i] > -1) {
             if (str[i + pArr[i]] == str[i - pArr[i]]) {
                 pArr[i]++;
             } else {
                 break;
             }
         }
         if (i + pArr[i] > R) {
             R = i + pArr[i];
             C = i;
         }
         if (max < pArr[i]) {
             max = pArr[i];
             mid = i;
         }
     }
     mid = (mid - 1) / 2;
     max = max - 1;
     return s.substring((max & 1) == 0 ? mid - (max / 2) + 1 : mid - (max / 2), mid + (max / 2) + 1);
 }
public static char[] manacherString(String str) {
    char[] charArr = str.toCharArray();
    char[] res = new char[str.length() * 2 + 1];
    int index = 0;
    for (int i = 0; i < res.length; i++) {
        res[i] = (i & 1) == 0 ? '#' : charArr[index++];
    }
    return res;
}