最长的回文子串

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

暴力法

找出所有的子串，判断它是不是回文串

• 时间复杂度O(n^3)

暴力法优化(动态规划)

首先定义一个二维数组 P(i,j),

接下来
P(i,j) = (P(i+1,j-1) && S[i]==S[j])
因此，我们不需要去判断S[i,j]是不是回文串，而是通过P(i+1,j-1)和S[i]==S[j]判断，这样时间复杂度减少了O(n)，利用动态规划，空间换时间

求 长度为 1 和长度为 2 的 P(i,j) 时不能用上边的公式，因为我们代入公式后会遇到 P[i][j] 中 i > j 的情况，比如求 P[1][2] 的话，我们需要知道 P[1+1][2-1]=P[2][1]P[1+1][2−1]=P[2][1] ，而 P[2][1]P[2][1] 代表着 S[2,1] 是不是回文串，显然是不对的，所以我们需要单独判断。

所以我们先初始化长度是 1 的回文串的 P[i,j]，这样利用上边提出的公式 P(i,j)=(P(i+1,j−1)&&S[i]==S[j])，然后两边向外各扩充一个字符，长度为 3 的，为 5 的，所有奇数长度的就都求出来了。
同理，先初始化长度为2的回文串，然后所有偶数长度也能求出

代码实现

public String longestPalindrome(String s) {
    int length = s.length();
    boolean[][] P = new boolean[length][length];
    String ans = "";
    int ansLen = 0;

    for(int len = 1; len <= length; len++){//遍历所有长度的子串，1~length
        for(int start = 0; start < length; start++){
            int end = start + len - 1;
            if(end >= length)//越界
                break;
            
            P[start][end] = (len==1 || len == 2 || P[start+1][end-1]) && s.charAt(start) == s.charAt(end);
            if(len>ansLen && P[start][end]){
                ansLen = len;
                ans = s.substring(start,end+1);
            }
        }
    }

    return ans;
}

中心扩散法

事实上，只需使用恒定的空间，我们就可以在O(n^2)的时间内解决这个问题。

我们观察到回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有 2n−1 个这样的中心。

你可能会问，为什么会是 2n−1 个，而不是 n 个中心？原因在于所含字母数为偶数的回文的中心可以处于两字母之间的间隙（例如 “abba” 的中心在两个 ‘b’ 之间）。

代码实现

public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";

    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);//字符
        int len2 = expandAroundCenter(s, i, i + 1);//间隙
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    //left == right，则以字符为中心，传出一个奇数
    //反之，以i，j的间隙为中心，传出一个偶数
    int L = left, R = right;
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    // 这里要小心，跳出 while 循环时，已经不满足 s.charAt(L) == s.charAt(R)
    // 因此L，R与实际匹配的位置多了一次自增自减，因此要 R-L-1,不然原本应该为 R-L+1
    return R - L - 1;
}

Manacher(马拉车) 算法

TBD