最大回文判断：
1.动态规划(时间长)
int [][] arr;//代表 i 到 j 44最大回文的长度（非回文，长度为max,）
P（i，j）为1时代表字符串Si到Sj是一个回文，为0时代表字符串Si到Sj不是一个回文。
P（i，j）= P（i+1，j-1）（如果S[i] = S[j]）。这是动态规划的状态转移方程。
2.Manacher算法
http://www.cnblogs.com/biyeymyhjob/archive/2012/10/04/2711527.html
字符串回文长度为奇数和偶数的情况均可同时解决:
id和mx，其中id表示最大回文子串中心的位置，mx则为id+P[id]，也就是最大回文子串的边界。
算法的关键点就在这里了：如果mx > i，那么P[i] >= MIN(P[2 * id - i], mx - i)。
P［id］记录的是以字符str［id］为中心的最长回文串，当以str［id］为第一个字符，这个最长回文串向右延伸了P［id］个字符。P［id］-1就是该回文子串在原串中的长度（包括‘#’）。for(; str[i+p[i]] == str[i-p[i]]; p[i]++)
这个算法是线性从前往后扫的。那么当我们准备求P［i］的时候，i以前的P［j］我们是已经得到了的。我们用mx记在i之前的回文串中，延伸至最右端的位置。同时用id这个变量记下取得这个最优mx时的id值。（注：为了防止字符比较的时候越界，我在这个加了‘#’的字符串之前还加了另一个特殊字符‘$’，故我的新串下标是从1开始的） 好，到这里，我们可以先贴一份代码了。
import java.io.FileNotFoundException; import java.util.Scanner; public class Main { public static int getPalindromeLength(String str) { // 1.构造新的字符串 // 为了避免奇数回文和偶数回文的不同处理问题，在原字符串中插入'#'，将所有回文变成奇数回文 StringBuilder newStr = new StringBuilder(); newStr.append('#'); for (int i = 0; i < str.length(); i ++) { newStr.append(str.charAt(i)); newStr.append('#'); } // rad[i]表示以i为中心的回文的最大半径，i至少为1，即该字符本身 int [] rad = new int[newStr.length()]; // right表示已知的回文中，最右的边界的坐标 int right = -1; // id表示已知的回文中，拥有最右边界的回文的中点坐标 int id = -1; // 2.计算所有的rad // 这个算法是O(n)的，因为right只会随着里层while的迭代而增长，不会减少。 for (int i = 0; i < newStr.length(); i ++) { // 2.1.确定一个最小的半径 int r = 1; if (i <= right) { r = Math.min(rad[id] - i + id, rad[2 * id - i]); } // 2.2.尝试更大的半径 while (i - r >= 0 && i + r < newStr.length() && newStr.charAt(i - r) == newStr.charAt(i + r)) { r++; } // 2.3.更新边界和回文中心坐标 if (i + r - 1> right) { right = i + r - 1; id = i; } rad[i] = r; } // 3.扫描一遍rad数组，找出最大的半径 int maxLength = 0; for (int r : rad) { if (r > maxLength) { maxLength = r; } } return maxLength - 1; } public static void main(String[] args) throws FileNotFoundException { int caseNum = 0; Scanner sc = new Scanner(System.in); while (true) { String str = sc.nextLine(); if (str.equals("END")) { break; } else { caseNum ++; System.out.println("Case " + caseNum + ": " + getPalindromeLength(str)); } } } } public class Solution { public String longestPalindrome(String s) { int id=1;//回文中心, int[] r;//记录以i为中心的最大半径 int mx=1;//记录最大回文边界 String ss="$#"; //1.奇偶性处理 for(int i=0;i<s.length();i++){ ss+=s.charAt(i); ss+="#"; } //2. int max=0,ii=0; r=new int[ss.length()]; for(int i=1;i<ss.length();i++){ if(i<mx){r[i]=Math.min(r[2*id-i], mx-i);}else{r[i]=1;} try{while(ss.charAt(i-r[i])==ss.charAt(i+r[i])){r[i]++;}} catch(Exception e){} if(r[i]+i>mx){mx=r[i]+i;id=i;} if(r[i]>max){max=r[i];ii=i;} } //3.找出最大半径 ss=ss.substring(ii-max+1, ii+max); String sss=""; for(int i=0;i<ss.length();i++){ if(ss.charAt(i)!='#'){sss+=ss.charAt(i);} } return sss; } }