Q:求一个字符串的最长回文子串
A:经典问题
public class 最长回文子串
{
//第一步先决策出最长的子串的长度
public static boolean[][] first(char[] arr)
{
boolean[][] dp=new boolean[arr.length][arr.length];
for (int i=0;i<arr.length-1 ;i++ )
{
dp[i][i]=true;
if (arr[i]==arr[i+1])
{
dp[i][i+1]=true;
}
}
dp[arr.length-1][arr.length-1]=true;
for (int len=3;len<=arr.length ;len++ )
{
for (int i=0;i<=arr.length-len ;i++ )
{
//i=arr.length-len时，j刚好为arr.length-1
int j=i+len-1;
if (arr[i]==arr[j]&&dp[i+1][j-1])
{
dp[i][j]=true;
}
}
}
return dp;
}
//第二步从第一步的决策，还原出最长的子串
public static String second(char[] arr,boolean[][] dp)
{
String str=null;
int len=arr.length-1;
int i=0;
outer:
while (len>0)
{
i=0;
for (int j=i+len;j<=arr.length-1 ;i++,j++ )
{
if (dp[i][j])
{
str= new String(arr,i,j-i+1);
break outer;
}
}
len--;
}
return str;
}
public static void main(String[] args)
{
String str="AABACD";
char[] arr=str.toCharArray();
boolean[][] dp=first(arr);
System.out.println(second(arr,dp));
}
}
