题解 | #最长回文子串#

添加字符#使得目标串的长度为奇数，例如: abc 变成 #a#b#c#; 然后遍历改变后的串，定义左右指针来判断是否是回文串

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 最长回文字串
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String bf = new String(sc.nextLine());// 最长回文字串匹配算法，Manacher 算法
            char[] bfChar = new char[bf.length() + 1 + bf.length()];// 保证是奇数
            int[] res = new int[bf.length() + 1 + bf.length()];
            for(int i = 0,j = 0; i < bf.length() * 2 + 1;i++){
                if(i % 2 ==  0) bfChar[i] = '#';
                else {
                    bfChar[i] = bf.charAt(j);j++;
                }
            }
            int maxSame = 0;// 保存当前计算的结果
            int left = 1;// 左右两个指针
            int right = 1;
            for(int i = 0;i < bf.length() * 2 + 1;i++) {
                // 先从第一个字符开始匹配,从左右走，如果遇到不相等的就结束
                left = i - 1;
                right = i + 1;
                maxSame = 0;
                while (true) {
                    if(left < 0 || right > bf.length() * 2) break;
                    if (i == 0 || i == bf.length() * 2) {res[i] = 0;break;}// 如果本来就是数组的边界，那么肯定回文串的长度就是0
                    else if (bfChar[left] != bfChar[right]) {// 如果左右两个字符都不相等的话，那么就是此时的结果就是
                        res[i] = maxSame;
                        break;
                    } else {
                        // 两个字符相等
                        left--;
                        right++;
                        maxSame++;
                        res[i] = maxSame;
                    }
                }
            }
            maxSame = -1;
            for(int i = 0;i < res.length;i++)
                if(res[i] > maxSame) maxSame = res[i];
            System.out.println(maxSame);

        }
    }
}