题解 | #进阶的回文串#

详细请看代码和图解：

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    String s = scanner.next();
    int n = s.length();
    
    // 判断长度x到y 是否是回文 的布尔集合，x=y时表示单体，isisPalindrome[x][y]=false 表示x到y的长度的字符串不是回文
    boolean[][] isisPalindrome = new boolean[n][n];

    // 表示长度x到y 回文阶数 的集合, order[x][y]=0 表示x到y的长度 时阶数为0，即不是回文
    int[][] order = new int[n][n];

    // 结果集，即最后的输出【专门搞一个输出数组的原因是题目要求输出每个阶数的数量，要知道一个阶数k的回文同时也是阶数 1 到 k-1 阶数的回文】
    int[] result = new int[n + 1];

    // ！！！下面是代码逻辑处理：
    // 特殊1，x到y的长度为1时所有单体都是1阶回文
    for (int x = 0; x < n; ++x) {
        int y = x;
        isisPalindrome[x][y] = true;
        order[x][y] = 1;
    }
    // 特殊2，判断x到y长度为2时是否是2阶回文【注意如果符合条件，它肯定也是一阶回文，这里先统计最高阶，后续再考虑分别输出阶数】
    for(int x = 0;x < n-1;++x){
        int y = x+1;
        if(s.charAt(x) == s.charAt(y)){
            isisPalindrome[x][y] = true;
            order[x][y]=2;
        }else{
            isisPalindrome[x][y] = false;
            order[x][y]=0;
        }
    }
    //由特殊1+特殊2来反推当x到y的长度 >= 3时的情况
    for(int len = 3;len <= n;len++){
        for(int x = 0; x + len <= n;++x){
            int y = len + x - 1;
            if(s.charAt(x) == s.charAt(y) && isisPalindrome[x+1][y-1]){
                int size = len / 2 ;
                int left = order[x][x + size - 1];
                int right = order[y - size + 1][y];
                // 这里进行min判断，就是因为会有特例，例如abcdcba，它属于1阶，不是2阶，它的左右部分是abc、cba并不是回文；这时因为前面设置不是回文的数字为 order[x][y]=0 的原因，Math.min(left,right) = 0，1 + 0 = 1，故abcdcba被判断为1阶
                int currentorder = 1 + Math.min(left,right);
                isisPalindrome[x][y] = true;
                order[x][y]=currentorder;
            }else{
                isisPalindrome[x][y] = false;
                order[x][y]=0;
            }
        }
    }

    // 得到所有情况下的最高阶数后，进行统计，例如aaaa即是3阶回文串，也是2和1阶回文
    int k;
    for (int i = 0; i < n; ++i ) {
        for (int j = i; j < n; ++j) {
            k = order[i][j];
            if (k > 0) {
                for (int z = k; z > 0; --z) {
                    result[z]++;
                }
            }
        }
    }
    // 输出最后结果
    for (k = 1; k <= n; ++k) {
        System.out.print(result[k] + " ");
    }
}

}