题解 | #密码截取#

import java.util.Scanner;
//最长回文子串问题：中心扩散法
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Main main=new Main();
        while (in.hasNext()) {
            String str = in.nextLine();
            System.out.println(main.longestPel(str));
        }
    }
    public int longestPel(String s)
    {
        int res=0;
        for (int i=0;i<s.length();i++)
        {
            res=Math.max(res,extend(s,i,i));
            res=Math.max(res,extend(s,i,i+1));
        }
        return res;
    }
    //以i和j作为中心向外扩散的回文串的长度
    public int extend(String s,int i,int j)
    {
        while (i>=0 && j<s.length() && s.charAt(i)==s.charAt(j))
        {
            i--;
            j++;
        }
        return j-i-1;
    }
}

最长回文子串问题

中心扩散法：从字符串的第一个字符开始依次选择,i,i, 和i,i+1作为中心向外扩散获得以该索引作为中心得到的子串的最长长度。

当整个字符串遍历一遍之后，不断更新记录到的最长子串长度。

动态规划法：

设置一个二维动态规划数组，如果dp[i][j]表示以i开头j结尾的字符串是否是回文串，如果是的话记录其长度并不断更新回文串的最大长度。