Java机试题*：密码截取（最长回文子串）

描述

Catcher是MCA国的情报员，他工作时发现敌国会用一些对称的密码进行通信，比如像这些ABBA，ABA，A，123321，但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化 ABBA->12ABBA,ABA->ABAKK,123321->51233214　。因为截获的串太长了，而且存在多种可能的情况（abaaab可看作是aba,或baaab的加密形式），Cathcer的工作量实在是太大了，他只能向电脑高手求助，你能帮Catcher找出最长的有效密码串吗？     数据范围：字符串长度满足 

输入描述：

输入一个字符串（字符串的长度不超过2500）

输出描述：

返回有效密码串的最大长度

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;



public class Main {
    /**
     * 思路一：找出所有子串，找出最大的有效子串长度（使用字符串翻转后与翻转前相同则是有效的。）本地所有用例有可以通过，机试编辑器里有些无法通过，估计题库有bug
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String str = sc.nextLine();
            List strs = new ArrayList();
            if(str.length() == 1) {
                strs.add(str);
            } else {
                for (int i = 0; i < str.length(); i++) {
                    for (int j = i+1; j <= str.length(); j++) {
                        strs.add(str.substring(i,j));
                    }
                }
            }
            int max = -1;
            StringBuffer sb;
            String temp;
            for (int i = 0; i < strs.size(); i++) {
                sb = new StringBuffer();
                sb.append(strs.get(i));
                temp = sb.reverse().toString();
                if(strs.get(i).equals(temp) && max < strs.get(i).length()) {
                    max = strs.get(i).length();
                }
            }
            System.out.println(max);
        }
    }

}

import java.util.Scanner;
public class Main {
    /**
     * 
     思路二 ： 最长回文子串的中心扩散法，遍历每个字符作为中间位，进行左右比较
     算法流程：
     从右到左，对每个字符进行遍历处理，并且每个字符要处理两次，因为回文子串有两种情况：
     ABA型：只需要从当前字符向两边扩散，比较左右字符是否相等，找出以当前字符为中心的最长回文子串长度
     ABBA型：只需要从当前字符和下一个字符向两边扩散，比较左右字符是否相等，找出以当前字符和下一个字符为中心的最长回文子串长度
     最后比对两种类型的长度，取自较长的长度
    */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(solution(s));
    }
    
    private static int solution(String s) {
        int res = 0;
        for(int i = 0; i < s.length(); i++) {
            // ABA型
            int len1 = longest(s, i, i);
            // ABBA型
            int len2 = longest(s, i, i + 1);
            res = Math.max(res, len1 > len2 ? len1 : len2);
        }
        return res;
    }
    
    private static int longest(String s, int l, int r) {
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return r - l - 1;
    }
}

题目来源：牛客网

参考链接：https://www.nowcoder.com/practice/3cd4621963e8454594f00199f4536bb1?tpId=37&&tqId=21255&rp=1&ru=/ta/huawei&qru=/ta/huawei/question-ranking