最长回文字串(java代码)

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        System.out.println(longestPalindrome(s));
    }

    /**                     0  1  2  3  4  5
                            a  b  c  a  a  c
                  0    a    T  F  F  F  F  F
                  1    b       T  F  F  F  F
                  2    c          T  F  F  T       4   caac
                  3    a             T  T  F       2    aa
                  4    a                T  F
                  5    c                   T

     */
    public static String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) return s;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[n][n];
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        // 记录回文子串的长度
        int max = 1;
        // 记录回文字串的初始下标
        int cs = 0;
        for (int j = 1; j < n; j++) {       // 列
            for (int i = 0; i < j; i++) {   // 行
                if (s.charAt(i) != s.charAt(j)){  // 判断字串两头是否相同，相同的才有是回文串
                    dp[i][j] = false;
                }else {
                    // 如果字串两头相等，那么如果里面的字串为0或者1就肯定为回文串，比如bab，bb。
                    if (j - i < 3){
                        dp[i][j] = true;
                    }else {
                        // 如果两头相同，里面字串长度也大于1，而我们是先计算里面的字符串，所以直接参考前面的就行
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                // 拿到最长的回文子串，和最长回文字串的位置。
                if (dp[i][j] && max < j - i +1){
                    max = j-i+1;
                    cs = i;
                }
            }
        }
        return s.substring(cs,cs+max);
    }
}