5.最长回文子串（马拉车怨种版）

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"
 

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

思路就是马拉车这个算法，对我来说实现的难度主要是在如何用java写，java的string类用的还是不熟练欸。

首先介绍一下马拉车算法，作为一个比较冷门的字符串处理方法，理解起来难度比好多了。

首先我们考虑这样一个问题，就是回文子串的长度分为两种， 一种是奇数，一种是偶数。

 如果是奇数的话就是这样的：   ababa

如果是偶数的话就是这样的：   aabbaa

但是如果是偶数的话，我们确实不方便处理，因此我们首先考虑如何吧偶数串，转化为奇数串？

我们的方法是，在收尾添加两个不同的字符，然后每个原有的字符前面后面都加一个#号。

这样我们的字符串：比如说奇数的aba就变成了￥#a#b#b#a#^

这样我们的回文字符串就变成了#a#b#b#a#是个奇数

void init()
{
    int k = 0;
    b[k ++ ] = '$', b[k ++ ] = '#';
    for (int i = 0; i < n; i ++ ) b[k ++ ] = a[i], b[k ++ ] = '#';
    b[k ++ ] = '^';
    n = k;
}

然后我们需要求一个叫p[i]的数组

p代表着转化后的字符串的”半径“

#a#b#b#a#的半径就是#a#b#长度为5， 里面一共有5 - 1个字符， 也就代表着，我们原来的字符串长度为4；

那么问题来了，我们如何求这个p呢？

首先我们要明确这样一件事情，p数组对应的字符串是我们插入#后的字符串， p[i] - 1对应的就是该回文子串在原来字符串的长度

p[i]表示的是以新字符串b[i]为中心的最长回文子串最右字符到b[i]的距离，也包括b[i]

计算，我们首先要引入两个变量，一个是mid， 一个是mr；

mid表示最大回文串中心的位置，

mr = id + p[id]， 代表最大回文子串的有边界

我们要分情况讨论，根据，i和mr的关系来确定。

第一种是i

第二种是i>= mr;

第一种情况由于我们的i已经小于mr了，说明，在我们当前的最大回文子串 p[mid]中，也有一个p[j]==p[i]， 而且由于他俩是对称的，所以会导致：i + j == 2 * mid;

我们就求得j = 2 * mid - i;

这时候我们就要考虑如何用p[j]去更新p[i]

i

我们现在的i距离mr的距离是mr - i；

        如果p[j] > mr - i; 说明 以 j为中心的回文子串， 左边已经超出了 我们当前最大回文子串的左边界，由于这个回文串对称性， 我们可以知道如果让p[i]等于p[j]的话，当前的条件是，p[i]右边超出mr的那一部分也必须是回文串的一部分，但是这一部分又难以预料，我们还没有求，所以说， p[j] > mr - i; 的情况下，p[i]就是等于mr - i；

        但是如果p[j] <= mr - i;说明，当前j 为中心的回文子串，全部都在最大回文串的内部，对称性可知，这时候的p[i] == p[j]；

再去处理i>= mr;的情况

由于我们i已经大于mr了，外边的都没有匹配到p[mid]里面去，我们只能暂时让p[i]等于一

if (i < mr) {
            p[i] = min(p[mid * 2 - i], mr - i);
        } else p[i] = 1;

最后我们为了解决 i < mr && p[i] > mr - i;和 i >= mr 的情况，我们只能采取向两边拓展的方式：

while (b[i - p[i]] == b[i + p[i]]) p[i] ++;

最后更新mr和mid；

如果i + p[i] > mr, 说明说明以i为中心的回文字串超过的边界mr， 就需要更新

if (i + p[i] > mr) {
            mr = i + p[i];
            mid = i;
        }

 最后是总结一下java用到的函数：

String的charAt

Math.min();

s.substring();

ok跑路，写了好久这篇哈哈哈

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        char[] a = new char[n * 2 + 1 + 3];
        int[] p = new int[n * 2 + 1 + 3];
 
        int k = 0;
        a[k ++] = '$';
        a[k ++] = '#';
        for (int i1 = 0; i1 < n; i1 ++) {
           a[k ++] = s.charAt(i1);
           a[k ++] = '#';
        }
        a[k ++] = '^';
        n = k;
        int mr = 0;
        int mid = 0;
        for (int i = 1; i < k; i ++) {
            if (i < mr) p[i] = Math.min(p[mid * 2 - i], mr - i);
            else p[i] = 1;
            while (a[i - p[i]] == a[i + p[i]]) p[i] ++;
            if (i + p[i] > mr) {
                mr = i + p[i];
                mid = i;
            } 
        }
 
        int ans = 0;
        int res = 0;
        for (int i = 0; i < n ; i ++) {
            if (res < p[i]) {
                ans = i;
                res = p[i];
            }
        }
        res --;
        if (ans % 2 == 1) { // 是成双成对的
            ans = ans / 2 - 1; // 得到的是在子串中，中间偏左的下标
            return s.substring(ans - (res / 2) + 1, ans + (res / 2) + 1);
        } else {
            ans = ans / 2 - 1;
            return s.substring(ans - (res / 2), ans + (res / 2) + 1);
        }
        //System.out.println(res);
        //eturn " ";
    }
}