Manacher算法

• 问题描述
• 常规思路
• Manacher思路
• 代码实现

问题描述

• Manacher算法解决的问题：
  （1）字符串str中，最长回文子串的长度如何求解
  （2）如何做到时间复杂度O(N)完成？

常规思路

• 遍历每个字符，将每个字符看成一个中心（对称轴），分别向左右扩展，相同就继续扩展，不同就结束
• 缺点：偶数个字符的回文，中心（对称轴）不是单个字符，会被忽略
• 解决技巧：处理长度为n的字符时，在原字符的空隙之间添加特殊字符，此时偶数个字符的回文以可转化成奇数个的去解决
• 例：
  （1）原字符：1 2 2 1 3 1 2 2 1 若统计1 2 2 1 就会出现忽略
  （2）添加特殊字符：# 1 # 2 # 2 # 1 # 3 # 1 # 2 # 2 # 1 # ，此时的回文均为奇数个，便都可以进行统计
• 统计出最长的回文，因为添加了特殊字符，所以结果除以2后向下取整，便是答案
• 特殊字符的选择：特殊字符可以是任意的，就算是原字符中出现过的也可以，因为其实每次比较是都是原来字符之间比较，新填的字符之间比较，所以特殊字符的选择不影响记录
• 时间复杂度O(N ^ 2)，N为字符个数

Manacher思路

• Manacher与kmp类似均是在常规思路的基础上进行加速
• 在常规思路添加特殊字符的基础上进行改进
• 基本概念：
  （1）回文半径与回文直径：扩充区域的大小
  （2）回文半径数组：记录每一个字符的回文半径
  （3）回文右边界：int型，初始值为 -1， 右扩的过程中能达到的最右边界的后一个位置
  （4）回文中心点：int型，初始值为 -1， 右扩的过程中达到的最右边界时，中心点的下标
  （5）回文右边界与中心点是一起使用的，同时进行更新
• 情况分析：
  （1）当前点 i 不在回文右边界里：暴力扩充，无优化，直接扩
  （2）当前点 i 在回文右边界里：
  L：左边界，R：右边界，C：中心点，i‘ ：i 关于C的对称点
  在回文半径数组中可以得到，i’ 的回文情况
  (a ) i’ 的回文区域在L内部，则 i 的回文半径就是 i‘ 的回文半径
  (b ) i’ 的回文区域有一部分已经在L外部，那么 i 的回文半径就是 i 到 R的部分
  (c ) i‘ 的回文区域与L重合，i 的回文半径一定 >= i 到 R 的部分，需要对R 后的东西与R关于 i 的对称点 R’ 进行比较，判断回文区域
• 时间复杂度O(N)，N为字符个数

代码实现

• 若使用情况分析的结果挨个判断实现代码太过繁琐
• 可以整合无需判断回文的部分，得到对应的回文半径后，跳过无需判断的部分后，剩余代码部分情况全部判断是否能扩张
  （1）情况1，无需比较的部分就是自己回文半径从1开始
  （2）情况2，a的情况是最小值，b与c都是基于回文右边界 - i，则比较preArr[ i‘ ] 与 R - i + 1的大小，取较小值就是不用判断的部分

    public static int manacher(String str){
        if (str == null || str.length() == 0){
            return 0;
        }
        char[] chs = manacherString(str); //添加特殊字符
        int[] preArr = new int[chs.length]; //回文半径数组
        int mid = -1; //回文中心
        int R = -1; //回文右边界
        int max = Integer.MIN_VALUE; //最大回文长度
        for (int i = 0; i < chs.length; i++){
            //遍历字符数组
            //不用判断的区域
            //i <= R当前点i不在右边界，回文半径至少是 1
            //i在右边界的两种情况：i'的回文在 L内，或者L外i
            //通过对称点 i’ 或者 R - i中的最小值，就可判断时哪一种情况
            preArr[i] = R > i ? Math.min(preArr[2 * mid - i], R - i + 1) : 1;
            while (i + preArr[i] < chs.length && i - preArr[i] > -1) {
                //不超过左右字符数组的情况下
                //无论是哪一种情况都判断能否扩张，使得代码精简
                if (chs[i + preArr[i]] == chs[i - preArr[i]]){
                    //满足扩展
                    preArr[i]++;
                }else {
                    break;
                }
            }
            if (i + preArr[i] > R){
            	//更新R，mid
                R = i + preArr[i] - 1;
                mid = i;
            }
            max = Math.max(max, preArr[i]);
        }
        //原字符串是扩充串回文半径 - 1
        return max - 1;
    }

    public static char[] manacherString(String str) {
        //添加特殊字符，使得回文字符的长度全部变成偶数
        char[] strArr = str.toCharArray();
        char[] chs = new char[str.length() * 2 + 1];
        for (int i = 0, j = 0; i < chs.length; i++){
            //偶数位置加入特殊字符
            chs[i] = (i & 1) == 0 ? '#' : strArr[j++];
        }
        return chs;
    }