算法之字符串——最长回文子串

最长回文子串

难度中等:smirk:
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

众所周知,回文子串是以某一轴为中心,左右呈镜像对称,如何找到 s 中最长的回文子串呢?

1.暴力破解

暴力破解是最容易想到的一种解法,即以每个字符为中心,向左右两边扩,看扩出去的范围有多大,同时记录一个最大值。比如 s = "abhba",最大回文子串即以 字符 h 为中心,左右扩到底。然而这种方法有个问题,无法应对偶回文:cold_sweat:,当 s ="abba"的时候,以每个字符为中心扩结果得到的最长回文子串长度为 1 !明显是错误的!
所以为了解决上述无法应对偶回文的情况,需要引入特殊字符来解决,即在每一个字符左右添加上一个特殊字符进行占位:smiley:,这样就可以解决这个问题
上述的 s ="abba" 就变成了 s ="#a#b#b#a#",这样我们就可以通过暴力法解决!

以下为暴力法的代码

public char[] getSPString(String s){
        int len = s.length();
        char[] arr = new char[2 * len + 1];
        for(int i = 0 ;i < len;i++){
            arr[2 * i] = '#';
            arr[2 * i + 1] = s.charAt(i);
        }
        arr[2 * len] = '#';
        return  arr;
    }
    public String longestPalindrome(String s) {
        if(s == null || s.length() <= 1){
            return s;
        }
        char[] res = getSPString(s);
        int len = res.length;
        int C = 0;   //最长回文串中心
        int max = 1;  //最长回文串长度

        for(int i = 0; i< len;i++){
            int j = 1;
            while(i - j >=0 && j + i < len){
                if(res[i - j] ==  res[i + j]){
                    j++;
                }else{
                    break;
                }
            }
            if(2 * j - 1 > max){
                C = i;
                max = 2 * j - 1;
            }   
        }
        return s.substring((C - max/2)/2 , (C+ max/2)/2);
    }

算法之字符串——最长回文子串

2.Manacher算法

暴力法的缺点在于,最坏情况下时间复杂度趋近于 O(n^2)!
而马拉车算法的关键在于通过定义一个最大右边界,不断地判断当前位置地情况,然后寻找当前位置地对称点,利用之前已经求出的信息,加速整个判断过程!注意:此过程也需要预先转换成特殊字符串进行处理!!!

:one:首先我们定义几个概念::eyes: :eyes: :eyes:
  1. 最大回文右边界 R :即当前字符串中的回文子串达到的最右位置。例如 “#a#b#c#b#a#c#”,当到达第一个字符 ‘c’ 时,最大回文右边界为下标10!
  2. 最大回文半径 max_Radius 和 存放对应位置的最大回文半径arr[ ] 数组: 回文半径就是当前回文中心到达右边界或者左边界的距离。如下图所示

算法之字符串——最长回文子串

  1. 回文中心 C :即当前最大右边界R的情况下,回文串的中心,与最大会问右边界互为对应关系。
:two:接下来就是加速过程!
  1. 当前位置 i 在最大回文右边界 R 的外边——以当前位置为中心往外扩,并更新 RC
    当遍历到第一个字符’#’时,发现不能往外扩,即最大回文右边界就是下标 0 ,然后碰到 字符 ‘a’的时候,发现 i 大于 R ,故需要往外扩,然后发现能扩出去,即此时 R 到了下标 2! C 也更新为了 i !

算法之字符串——最长回文子串

  1. 当前位置 i 在最大回文右边界 R 的里边——判断 i 的对称点 i’ 的情况!
    此时需要分三种情况:

    • 以 i’ 为中心的最大回文子串完全在最大左边界即将最大右边界RC为中心对称过去)里边!如下图,此时 i 位置的最大回文半径 与 i’ 一样,都为 2!此时时间复杂度为O(1)

    • 以 i’ 为中心的最大回文子串超出最大左边界!如下图所示,此时 i’ 的回文串已经超出 L 到达了 左边的 K 字符,那么此时 i 的最大回文半径就是 R - i ,为什么此时不用扩呢?其实可以证明,如果此时可以扩,那么只有一种情况, 最右边的不是 E 而是 K ,但是如果是 K 的话,此时违反了 R 的最大回文右边界 的定义!即 R 一定至少大于等于最右边 E 的位置!所以此时 L 的左边一个字符和 R 右边的字符一定不等! 此时时间复杂度为O(1)

    • 以 i’ 为中心的最大回文子串正好在最大左边界上!即压线!如下图所示。此时以i位置为中心,以arr[i’]为半径,需要再往外扩!因为这时不确定 R 右边的字符是否满足条件!

综上,情况就是分为两大类,i 在回文右边界里边和外边!需要扩的两种情况,即 i 在 R 外边和压线,都是在不断地往右推动这个 R,所以整个过程总起来看就是在不断地往右推动着 R 前进,因为 R最多能到最右边,故整体的时间复杂度为 O(n)级别的!!!!!:boom: :boom: :boom:

下面直接上代码

public void manacher(String s) {
        if (s == null || s.length() <= 1) {
            return;
        }
        char[] sp = getSPString(s);
        int len = sp.length;
        int[] arr = new int[sp.length]; //最长回文半径数组
        int R = -1; //最大回文右边界
        int C = -1; //最大回文中心
        int max = -1; // 最长回文半径
        for (int i = 0; i < len; i++) {
            arr[i] = R > i ? Math.min(arr[2 * C - i] , R - i) : 1;
            while(i + arr[i] < len && i - arr[i] >= 0){
                if(sp[i + arr[i]] == sp[i - arr[i]]){
                    arr[i] ++;
                } else{
                    break;
                }
            }
            if(i + arr[i] > R){
                R = i +arr[i];
                C = i;
            }
            if(max < arr[i]){
                max  = arr[i];
                center = i;
            }
        }
    }

算法之字符串——最长回文子串

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!