美文网首页数据结构与算法
Manacher算法的详细讲解

Manacher算法的详细讲解

作者: 道禅_26ea | 来源:发表于2018-09-24 23:30 被阅读1141次

Manacher算法,又叫“马拉车”算法,可以在时间复杂度为O(n)的情况下求解一个字符串的最长回文子串长度的问题。

一、回文子串的一般解法

比较简单的思路是将字符串的每一个字符作为回文子串的中心对称点,每次保存前面求得的回文子串的最大值,最后得到的就是最长的回文子串的长度,这种方式的时间复杂度是O(n^2)。在求解过程中,基数的回文子串与偶数的回文子串是不一样的。比如最长回文子串为aba,对称中心就是b,如果最长回文子串为abba,则对称中心应该为两个b之间,为了解决这个问题,可以在每个字符两边加上一个符号,具体什么符号(是字符串里面的符号也行)对结果没有影响,比如加上“#”,则上述的两个序列变成了#a#b#a#和#a#b#b#a#,求出的长度分别为6和9,再除以2就可以得到最后的结果3和4。这种方式的时间复杂度太高,下面介绍时间复杂度为O(n)的Manacher算法。

二、Manacher算法中的基础概念

在进行Manacher算法时,字符串都会进行上面的进入一个字符处理,比如输入的字符为acbbcbds,用“#”字符处理之后的新字符串就是#a#c#b#b#c#b#d#s#。

1、回文半径数组radius

回文半径数组radius是用来记录以每个位置的字符为回文中心求出的回文半径长度,如下图所示,对于p1所指的位置radius[6]的回文半径是5,每个位置的回文半径组成的数组就是回文数组,所以#a#c#b#b#c#b#d#s#的回文半径数组为[1, 2, 1, 2, 1, 2, 5, 2, 1, 4, 1, 2, 1, 2, 1, 2, 1]。

要处理的字符串

2、最右回文右边界R

一个位置最右回文右边界指的是这个位置及之前的位置的回文子串,所到达的最右边的地方。比如对于字符串#a#c#b#b#c#b#d#s#,求它的每个位置的过程如下:

最右回文右边界R过程

最开始的时候R=-1,到p=0的位置,回文就是其本身,最右回文右边界R=0;p=1时,有回文串#a#,R=2;p=2时,R=2;P=3时,R=6;p=4时,最右回文右边界还是p=3时的右边界,R=6,依次类推。

3、最右回文右边界的对称中心C

就是上面提到的最右回文右边界的中心点C,如下图,p=4时,R=6,C=3

最右回文右边界的对称中心C

三、Manacher算法的流程

首先大的方面分为两种情况:

第一种情况:下一个要移动的位置在最右回文右边界R的右边。

比如在最开始时,R=-1,p的下一个移动的位置为p=0,p=0在R=-1的右边;p=0时,此时的R=0,p的下一个移动位置为p=1,也在R=0的右边。

在这种情况下,采用普遍的解法,将移动的位置为对称中心,向两边扩,同时更新回文半径数组,最右回文右边界R和最右回文右边界的对称中心C。

第二种情况:下一个要移动的位置就是最右回文右边界R或是在R的左边

在这种情况下又分为三种:

1、下一个要移动的位置p1不在最右回文右边界R右边,且cL<pL。

p2是p1以C为对称中心的对称点;

pL是以p2为对称中心的回文子串的左边界;

cL是以C为对称中心的回文子串的左边界。

这种情况下p1的回文半径就是p2的回文半径radius[p2]。

p1<=R且cL<pL

2、下一个要移动的位置票p1不在最右回文右边界R的右边,且cL>pL。

p2是p1以C为对称中心的对称点;

pL是以p2为对称中心的回文子串的左边界;

cL是以C为对称中心的回文子串的左边界。

这种情况下p1的回文半径就是p1到R的距离R-p1+1。

p1<=R且cL>pL

3、下一个要移动的位置票p1不在最右回文右边界R的右边,且cL=pL;

p2是p1以C为对称中心的对称点;

pL是以p2为对称中心的回文子串的左边界;

cL是以C为对称中心的回文子串的左边界。

这种情况下p1的回文半径就还要继续往外扩,但是只需要从R之后往外扩就可以了,扩了之后更新R和C。

p1<=R且cL==pL

四、Manacher时间复杂度分析

从上面的分析中,可以看出,第二种情况的1,2的求某个位置的回文半径的时间复杂度是O(1),对于第一种情况和第二种情况的3,R是不断的向外扩的,不会往回退,而且寻找回文半径时,R之内的位置是不是进行判断的,所以对整个字符串而且,R的移动是从字符串的起点移动到终点,时间复杂度是O(n),所以整个manacher的时间复杂度是O(n)。

五、Manacher的代码实现

public static void main(String[] args) {
        String str = "abcdcbafabcdck";
        //String str = "acbbcbds";
        System.out.println(manacher(str));
    }

    public static char[] manacherString(String str){
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            sb.append("#");
            sb.append(str.charAt(i));
        }
        sb.append("#");
        return sb.toString().toCharArray();
    }

    public static int manacher(String str){
        if(str == null || str.length() < 1){
            return 0;
        }
        char[] charArr = manacherString(str);
        int[] radius = new int[charArr.length];
        int R = -1;
        int c = -1;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < radius.length; i++) {
            radius[i] = R > i ? Math.min(radius[2*c-i],R-i+1):1;
            while(i+radius[i] < charArr.length && i - radius[i] > -1){
                if(charArr[i-radius[i]] == charArr[i+radius[i]]){
                    radius[i]++;
                }else{
                    break;
                }
            }
            if(i + radius[i] > R){
                R = i + radius[i]-1;
                c = i;
            }
            max = Math.max(max,radius[i]);
        } 
        return max-1;
    }

相关文章

  • Manacher算法的详细讲解

    Manacher算法,又叫“马拉车”算法,可以在时间复杂度为O(n)的情况下求解一个字符串的最长回文子串长度的问题...

  • Manacher算法(马拉车算法)

    Manacher算法(马拉车算法) Manacher算法,又叫“马拉车”算法,可以在时间复杂度为O(n)的情况下求...

  • 寻找字符串中的最长回文子串Manacher's Algo

    Manacher's Algorithm 马拉车算法

  • manacher算法

    概念:求字符串的最大回文串1.先处理成偶数串2.回文半径3.回文半径最右边界,并记录最早中心位置 扩展题 给定一个...

  • Manacher算法

    最长回文子串问题# 给定一个字符串,找出最长的回文子串,如"waabwswbfd",则最长子串为bwsb. 中心试...

  • Manacher算法

    前言 Manacher算法用于求解字符串中最长的回文子串,它和KMP算法的改进方式很类似,都是基于暴力求解的方法,...

  • Manacher算法

    看这样一道例题: hdoj-3068.最长回文 给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S...

  • Manacher算法

    首先让我们来看Leetcode上的一道题。 题意解析:给定一个字符串S,求这个字符串的最长回文子串。所谓回文字符串...

  • Manacher算法

    Manacher又叫"马拉车"算法,它可以在O(N)的平均时间复杂度下面找到一个字符串的最长回文子串。 题目 Le...

  • Manacher算法

网友评论

    本文标题:Manacher算法的详细讲解

    本文链接:https://www.haomeiwen.com/subject/knzhoftx.html