【算法】L2-008 最长对称子串 (25 分)Java，字符串典型例题

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;


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