美文网首页
Manacher 马拉车算法计算回文子串

Manacher 马拉车算法计算回文子串

作者: forping | 来源:发表于2020-12-04 10:38 被阅读0次

最近开始刷算法题,
在刷第五题的时候,看到一个有意思的算法,总结一下

计算回文子串,首先简单的有

暴力破解法,就是挨个循环,计算每两个字符之间是不是回文子串,如果是和当前保存的最大的回文子串比较
时间复杂度:O(N3),空间复杂度 O(1)

中心扩散 以每个字符为中心,计算回文串的长度,和当前保存的最大的回文子串比较.
时间复杂度:O(N2),空间复杂度O(1);

动态规划 声明一个二维数组,保存两个字符之间是不是回文子串的状态,如果两个字符(i,j)相等,那么 i+1,j-1 是回文子串,则(i,j) 也是回文子串,
注意事项:总是先得到小子串的回文判定,然后大子串才能参考小子串的判断结果,即填表顺序很重要。
时间复杂度O(N2),空间复杂度O(N2);

Manacher算法

Manacher 算法是基于“中心扩散法”,采用和 kmp 算法类似的思想,依然是“以空间换时间”。
使用了类似 KMP 算法的技巧,充分挖掘了已经进行回文判定的子串的特点,在遍历的过程中,记录了已经遍历过的子串的信息
时间复杂度 O(N), 空间复杂度O(N)

第 1 步:对原始字符串进行预处理(添加分隔符)

首先在字符串的首尾、相邻的字符中插入分隔符,例如 "babad" 添加分隔符 "#" 以后得到 "#b#a#b#a#d#"。

对这一点有如下说明:

  1. 分隔符是一个字符,种类也只有一个,并且这个字符一定不能是原始字符串中出现过的字符;
  2. 加入了分隔符以后,使得“间隙”有了具体的位置,方便后续的讨论,并且新字符串中的任意一个回文子串在原始字符串中的一定能找到唯一的一个回文子串与之对应,因此对新字符串的回文子串的研究就能得到原始字符串的回文子串;
  3. 新字符串的回文子串的长度一定是奇数;
  4. 新字符串的回文子串一定以分隔符作为两边的边界,因此分隔符起到“哨兵”的作用。
  private String addBoundaries(String s, char divide) {
        int len = s.length();
        if (len == 0) {
            return "";
        }
        if (s.indexOf(divide) != -1) {
            throw new IllegalArgumentException("参数错误,您传递的分割字符,在输入字符串中存在!");
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < len; i++) {
            stringBuilder.append(divide);
            stringBuilder.append(s.charAt(i));
        }
        stringBuilder.append(divide);
        return stringBuilder.toString();
    }

第 2 步:计算辅助数组 p

辅助数组 p 记录了新字符串中以每个字符为中心的回文子串的信息。
采取“中心扩散法”,此时记录以当前字符为中心,向左右两边同时扩散,能够扩散的最大步数。


image.png

第3步:更有效率的计算辅助数组p

需要一些辅助变量,
maxRight计算回文子串到字符串最右边的值.
center 和 maxRight 相关联的回文子串的中心
' mirror ' mirror 和 i 关于center对称, (i+mirror) /2 == center ,
可以通过 p[mirror] 计算出 p[i]的大致值.再进行中心扩散算法,如果 i+p[i] 超过了 maxRight,则center = i, maxRight = i+p[i];

  public String longestPalindrome(String s) {

        if (s.length()<2){
            return s;
        }

        String str = addBoundaries(s,'#');

        int strLen = str.length();

        // 数组 p 记录了扫描过的回文子串的信息
        int []p = new int[strLen];

        // 原始字符串的最长回文子串的起始位置,与 maxLen 必须同时更新
        int start = 0;
        // 当前遍历的中心最大扩散步数,其值等于原始字符串的最长回文子串的长度
        int maxLen = 0;

        // 双指针,它们是一一对应的,须同时更新
        int center = 0;
        int maxRight = 0;

        for (int i = 0; i<strLen; i++){
            if (i < maxRight){
                int mirror = 2*center - i;
                // 只是大概值,如果i+p[i] >= maxRight那么还需要中心扩散
                p[i] = Math.min(p[mirror], maxRight - i);
            }
            int left = i - p[i] -1;
            int right = i + p[i] + 1;
            // 中心扩散算法
            while((left >=0) && (right<str.length()) && (str.charAt(right) == str.charAt(left))){
                left--;
                right++;
                p[i]++;
            }

            // 更新center和maxright的值
            if (i + p[i]>maxRight){
                center = i;
                maxRight = i+p[i];
            }
            if (p[i] > maxLen){
                maxLen = p[i];
                start = (i - p[i])/2;// 除以2 是要计算原始子串的位置
            }
        }
        return s.substring(start,start+maxLen);
    }

参考链接
https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419/

相关文章

  • Manacher's Algorithm算法分析Java

    Manacher's Algorithm俗称马拉车算法,对于求字符串中最长回文子串效率极高。 在求最长回文子串的时...

  • Manacher 马拉车算法计算回文子串

    最近开始刷算法题,在刷第五题的时候,看到一个有意思的算法,总结一下 计算回文子串,首先简单的有 暴力破解法,就是挨...

  • 一文弄懂Manacher算法

    今天我们来介绍一下处理回文字符串的算法:Manacher(俗称“马拉车”)。 算法功能 回文字符串的通俗定义是:如...

  • Manacher算法的详细讲解

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

  • Manacher's Algorithm 的理解

    在 leetcode 刷题刷到求字符串的最长回文字串,而马拉车算法(Manacher's Algorithm), ...

  • Manacher算法

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

  • 最长回文子串

    最长回文子串——Manacher 算法 1. 问题定义 最长回文字符串问题:给定一个字符串,求它的最长回文子串长度...

  • 经典算法问题:最长回文子串之 Manacher 算法

    title: 经典算法问题:最长回文子串之 Manacher 算法date: 2019-02-17 08:00:0...

  • Manacher算法详解

    目录结构如下: 引入 Manacher算法详解 例题 References 1. 问题引入 最长回文子串(Long...

  • Manacher算法(马拉车算法)

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

网友评论

      本文标题:Manacher 马拉车算法计算回文子串

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