L2-008 最长对称子串 (25 分)
对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出11。
输入格式：
输入在一行中给出长度不超过1000的非空字符串。
输出格式：
在一行中输出最长对称子串的长度。
输入样例：
Is PAT&TAP symmetric?
结尾无空行
输出样例：
11
结尾无空行
这是一个典型的动态规划题
解法：
1：初始化一个dp表格，表格的行表示子串的头下表，表格的列表示子串的尾下标。故对角线上的值都为true
2：对表格的上三角进行列遍历，自左上向右下。若子串的长度为2时，第一个字符与第二个字符相当那么dp[i][j]=true。若长度大于2时，当s[i][j]相等时还需要对中间的子串进行判断。如图中的dp[0][4],需要判断dp[1][3]是否为true。
import java.util.Scanner;
/**
* L2-008 最长对称子串 (25 分)
* 对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出11。
*
* 输入格式：
* 输入在一行中给出长度不超过1000的非空字符串。
*
* 输出格式：
* 在一行中输出最长对称子串的长度。
*
* 输入样例：
* Is PAT&TAP symmetric?
* 结尾无空行
* 输出样例：
* 11
*/
public class L2_008 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String s=sc.nextLine();
System.out.println(longest(s));
}
public static int longest(String s){
int n=s.length();
if(s.length()<2)return n;
int count=1;
boolean dp[][]=new boolean[n][n];
//初始化对角线上的单个子串为true
for(int i=0;i<n;i++){
dp[i][i]=true;
}
char[] chars = s.toCharArray();
//自左上向右下遍历
//i表示子串的头，j表示子串的尾
for(int j=0;j<n;j++){
for(int i=0;i<j;i++){
//若
if(chars[i]!=chars[j])dp[i][j]=false;
else {
if(j-i<2)dp[i][j]=true;
else dp[i][j]=dp[i+1][j-1];
}
if(dp[i][j]==true){
count=Math.max(count,j-i+1);
}
}
}
return count;
}
}
?
?
?