随笔记录

算法-Manacher算法（最长回文子串、回文半径）

2022-5-5 diaba 算法

package com.jiucaiyuan.net.question;

/**
 * Manacher算法
 * 解决问题：字符串str中，最长回文子串的长度如何求解？
 * 如何做到时间复杂度O(N)完成？
 *
 * @Author jiucaiyuan  2022/5/2 13:29
 * @mail services@jiucaiyuan.net
 */

public class Manacher {

    /**
     * <pre>
     * <b>求输入字符s的最大回文子串（非子序列）</b>
     * <b>Manacher算法</b>（最长回文子串）
     * 【算法中概念】：
     *      R 最右回文边界 （代码中表示回文边界的下一个位置，为了写代码方便）
     *      C 最右回文边界R对应的回文中心位置
     *      L R关于C的对称点
     *      pArr 回文半径数组pArr[]，pArr[i]表示以i位置为中心找最大回文，得到的回文半径长度赋值给pArr[i]
     * 【不同情况处理】
     *      1）当前点，没有在最右回文边界R里（在R之外）
     *          暴力破
     *      2）当前点，相对C的对称点i`的回文区域在L和R内部（R相对C点的对称点是L）
     *          这时候i的回文半径和i`的回文半径一样
     *      3）当前点，相对C的对称点i`的回文区域，一部分跑到L的外面
     *          这时候i的回文半径是i到R距离（R-i）
     *      4）当前点，相对C的对称点i`的回文区域，左侧正好压在L上
     *          这时候i的回文半径从R开始，继续向右验证（i到R内不需要验证）
     * </pre>
     *
     * @param s
     * @return
     */
    public static int maxLengthPalindromeSubString(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = manacherString(s); //12321 ——> #1#2#3#2#1#
        int[] pArr = new int[str.length]; //回文半径数组，每个字符的回文半径组成的数组   经过下面for代码后，回文半径数组被填充了
        int C = -1;  //最右回文边界R对应的回文中心位置
        int R = -1; //最右回文边界再往右一个位置，最右的有效区是 R-1 位置
        int max = Integer.MIN_VALUE;  //扩出来的最大值

        for (int i = 0; i != str.length; i++) {  //每个位置都求回文半径

            //如果i在R外，不用验的区域是1
            //如果i在R内，Math.min(pArr[2 * C - i], R - i)        2 * C - i是i`的位置，R-i
            //所以i至少的回文半径区域赋值给pArr[i]
            //i<R  表示i在R内   各种情况不用验的区域都汇聚到此
            pArr[i] = i < R ? Math.min(pArr[2 * C - i], R - i) : 1;

            //不用验（是否回文的区域、加速）的区域确定后，并没有超过边界，继续进行尝试
            while (i + pArr[i] < str.length && i - pArr[i] > -1) {
                //不用验的区域确定后，再尝试往两边验证下是否相同，如果相同，回文半径++
                if (str[i + pArr[i]] == str[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }

            //如果扩完发现R可以变大，则记录最大回文半径R及对应的中点C
            if (i + pArr[i] > R) {
                R = i + pArr[i];
                C = i;
            }

            //记录以每个字符为中心往外扩找最大回文时的最长回文长度
            max = Math.max(max, pArr[i]);
        }

        //max是加特殊字符后的回文半径，原始串的回文长度正好等于加特殊字符后的回文半径-1
        return max - 1;
    }

    /**
     * 把输入的字符串加工成加入#字符的新字符数组
     * 如：输入"12345"，返回['#','1','#','2','#','3','#','4','#','5','#']
     * @param str 原始字符串
     * @return 原始字符串空隙加入特殊字符#后对应的字符数组
     */
    public static char[] manacherString(String str) {
        char[] charArr = str.toCharArray();
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : charArr[index++];
        }
        return res;
    }

    public static void main(String[] args) {
        String str = "abc1234321ab";
        System.out.println(str+"最长回文子串长度="+maxLengthPalindromeSubString(str));
    }

}