#密码截取#最长回文串

描述

Catcher是MCA国的情报员，他工作时发现敌国会用一些对称的密码进行通信，比如像这些ABBA，ABA，A，123321，但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。

比如进行下列变化 ABBA->12ABBA,ABA->ABAKK,123321->51233214。

因为截获的串太长了，而且存在多种可能的情况（abaaab可看作是aba,或baaab的加密形式），Cathcer的工作量实在是太大了，他只能向电脑高手求助，你能帮Catcher找出最长的有效密码串吗？ 数据范围：字符串长度满足1≤n≤2500

华为机试题（HJ32 密码截取）

思路

密码截取问题即查询一个字符串的最长回文串。 我们只需要计算出以当前字符串为中心的最长回文长度。当前为中心有两种情况： 奇数位：比如121，2为中心长度即为3。 偶数位：比如1221，22为中心，长度为4。 所以计算时也分两种情况，以当前字符为中心和以前字符+当前字符为中心进行对比。 代码如下：

import java.util.Scanner;
public class Main {
    private static Scanner in = new Scanner(System.in);
    public static void main(String[] args) {
        String input = in.nextLine();
        System.out.println(handleData(input));
    }

    //处理数据
    private static int handleData(String input) {
        int length = input.length();
        char[] word = input.toCharArray();
        int value = 1;
        for(int i = 1; i< length-1;i++){//从第二位开始
            int index = 1;
            //判断奇数位最长回文
            int val = 1;//回文值，奇数位定包含自己，默认为1
            while ((i-index >= 0)&&(i+index<=length-1)&&(word[i-index] == word[i+index])){
                val += 2;
                index++;
            }
            //判断偶数位
            int val2 = 0;//回文值，默认值为0
            index = 1;
            while ((i-index >= 0)&&(i+index<=length)&&(word[i-index] == word[i+index-1])){
                val2 += 2;
                index++;
            }
            value = Math.max(Math.max(val, val2), value);
        }
        return value;
    }
}

运行结果：

提交结果：答案正确 运行时间：51ms 占用内存：11708KB 使用语言：Java 用例通过率：100.00%