算法-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));
    }

}

发表评论:

Powered by emlog 京ICP备15045175号-1 Copyright © 2022