1 package com.ysw.test; 2  3 import java.util.Scanner; 4  5 /* 6  * 问题描述： 7  * 给定一个字符串S，找出它的最大的回文子串，你可以假设字符串的最大长度是1000， 8  * 而且存在唯一的最长回文子串 。 9  */10 public class LongestPalindrome {11 12     /**13      * @param args14      */15     public static void main(String[] args) {16         // 从键盘读入字符串17         String str = null;18         Scanner reader = new Scanner(System.in);19         str = reader.nextLine();20         System.out.println(getLongestPalindrome(str));21     }22 23     /**24      * 此方法返回s的最长回文串25      * 26      * @param str27      * @return28      */29     private static String getLongestPalindrome(String str) {30 31         boolean dp[][];32         // 如果字符串的长度为0，则认为str的最长回文串为空字符串33         if (str.length() == 0) {34             return "";35         }36         // 字符串str长度为1.则字符串本身就是一个最长回文串37         if (str.length() == 1) {38             return str;39         }40         // dp[i][j],表示字符串str从str[i]到str[j]的子串为最长回文子串41         dp = new boolean[str.length()][str.length()];42         // 记录已经找到的最长回文子串的长度43         int maxLen = 1;44         // 记录最长回文子串的起点位置和终点位置45         int start = 0, end = 0;46         // 动态规划的进行是按照字符串的长度从1 到 n推进的，k表示正在判断的子串的长度47         // 用于和已知的子串的长度maxLen进行比较48         int k;49         // 找出str的所有子串的dp对应的boolean值,初始化过程50         for (int i = 0; i < str.length(); i++) {51             for (int j = 0; j < str.length(); j++) {52                 // 当i==j的时候，只有一个字符的字符串53                 // 当i>j的时候认为是空串，dp[i][j]54                 if (i >= j) {55                     dp[i][j] = true;56                 } else {57                     dp[i][j] = false;58                 }59             }60         }61 62         // 我在这里犯了一个幼稚的错误，把i、j的定义放在了for循环中，在else{}中是访问不到的63         // 运行程序报java.lang.StringIndexOutOfBoundsException: String index out of64         // range错误65         int i, j;66         for (k = 1; k < str.length(); k++) {67             for (i = 0; i + k < str.length(); i++) {68 69                 j = i + k;70                 if (str.charAt(i) != str.charAt(j)) {71                     dp[i][j] = false;72                 } else {73                     dp[i][j] = dp[i + 1][j - 1];74                     if (dp[i][j]) {75                         // 判断找到的子串的长度是否大于我们已知的最长子串的长度76                         if (k + 1 > maxLen) {77                             // 记录最长回文子串78                             maxLen = k + 1;79                             // 记录子串的起始位置，因为后面的函数subString(int beginIndex,int80                             // endIndex)函数要用到81                             start = i;82                             end = j;83                         }84                     }85                 }86             }87         }88         return str.substring(start, end + 1);89     }90 }