C/C++教程

算法设计与分析 Manacher算法

本文主要是介绍算法设计与分析 Manacher算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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;
    }
这篇关于算法设计与分析 Manacher算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!