题解 | #密码截取#

分析：本题实质上就是找最长回文子串，可以参见*********，这里给出其中两种做法。

从中心出发找回文

简单分析就可以发现，如果使用暴力计算，枚举回文串的长度需要 O(n)，枚举回文串的起始位置需要 O(n)，判断是否对称（使用从中心开始向两边判断的最优方法）也需要 O(n)，这样的方法总共需要三阶 n 的级别，不能接受。

考虑我们判断是否对称时用的方法，从中心出发，向两边扩展，这个过程只需要枚举中心位置的值即可，用这种方法一共只需要二阶 n 就可以完成，输入串长度规模是 k 级别的，完全可以接受。

注意：判断的时候，中心有一个或两个（对应回文串为奇数长和偶数长的情况）。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            // 找最长回文子串
            char[] s = in.next().toCharArray();
            int maxLen = 0;
            for (int i = 0; i < s.length; i++) {
                int len;
                int l, r;
                // 以 s[i] 为中心
                len = 1;
                l = i - 1;
                r = i + 1;
                while (l >= 0 && r < s.length && s[l] == s[r]) {
                    len += 2;
                    l--;
                    r++;
                }
                maxLen = Math.max(maxLen, len);

                // 以 s[i], s[i+1] 为中心
                len = 0;
                l = i;
                r = i + 1;
                while (l >= 0 && r < s.length && s[l] == s[r]) {
                    len += 2;
                    l--;
                    r++;
                }
                maxLen = Math.max(maxLen, len);
            }
            System.out.println(maxLen);
        }

    }
}