5-最长回文子串-可能是最细致的马拉车(Manacher)算法

写在前面

这次带来的问题相信很多刷力扣的同学都刷过了,毕竟是第五道题,第一眼就能看到。暴力法、最长公共子串法、动态规划法、中心扩展法、马拉车算法都可以解决,前四个还好,比较好理解,不过马拉车算法是真的挺复杂、也挺玄妙的。本文先简述前四种方法,然后详解马拉车算法,有需要的读者还请直接看后面。(ps:查了半天也没找到简书的页内跳转,还请手动翻吧,大约在文章一半的位置开始马拉车算法)

题目

暴力法(超时)

核心思路

暴力法显然要遍历所有的可能,可以单独写一个函数判断字符串是否是回文串,然后两重循环遍历每一种可能即可;同样也可以使用下面这种反转字符串的暴力法,直接使用substring函数来判断是否是回文串。不过毕竟是超时的,就不多赘述。

代码

class Solution {
    public String longestPalindrome(String s) {
        String sr = new StringBuilder(s).reverse().toString();// 反向字符串
        String ans = "";
        int maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                if (s.substring(i, j).equals(sr.substring(s.length() - j, s.length() - i))) {
                    if (maxLen < j - i + 1) {
                        ans = s.substring(i, j);
                        maxLen = j - i + 1;
                    }
                }
            }
        }
        return ans;
    }
}

时间复杂度O(n³),时间占用恐怖,不能通过测试。

最长公共子串法

核心思路

这种方法同样要将字符串反转,我们考虑字符串 aabacaba ,其最长回文串为 abacaba ,由于回文串具有正读、反读字符串时相同的特性,所以反转字符串后,原字符串和反转字符串的最长公共子串即是最长回文串。
乍一看好像没有问题,不过考虑字符串 abcdecba,反转字符串与原字符串的最长公共子串为 abc 显然不是回文串。所以,在判断公共子串时,需要判断两者公共子串的下标是否是对应的。另外,求最长公共子串可以使用动态规划来在O(n)的复杂度完成。

代码

class Solution {
    public String longestPalindrome(String s) {
        String sr = new StringBuilder(s).reverse().toString();// 反向字符串
        String ans = "";
        int maxLen = 0;
        int[] dp = new int[s.length() + 1];//用动态规划来求公共子数组的长度
        int start = 0, end = 0;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = s.length(); j > 0; j--) {
                if (s.charAt(i - 1) == sr.charAt(j - 1)) {
                    dp[j] = dp[j - 1] + 1;
                    /* 判断下标是否与原字符串对应 */
                    if (maxLen < dp[j] && i - dp[j] == s.length() - j) {
                        //更新最长子串长度并计算开始和结束位置            
                        maxLen = dp[j];
                        start = i - maxLen;
                        end = i;

                    }
                }else{
                    dp[j] = 0;
                }
            }
        }
        ans = s.substring(start, end);
        return ans;
    }
}

时间复杂度O(n²),空间复杂度O(n),用动态规划求公共子数组的方法还是值得了解的,不过这种解法整体思路与暴力法差别不大,效率也不高。

动态规划法

核心思路

这道题我是按标签动态规划进去的,不过这道题真的不太典型,动态规划也没有提高多少时间效率,而且也不是很好想到,所以这种办法不像其他DP问题那样详细讲解。(可以参考windliang的力扣题解
既然采用DP思想,就要划分子问题,那这道题最小的问题便是最短的回文串: aaa,单回文串和双回文串。然后就要思考怎么递推,可以想到,如果一个串已经是回文串:aba,倘若其首尾两个字符相等:babab,则长的字符串也是回文串,否则他就不是回文串。所以,使用DP方法其实就是在判断某一子串是否为回文串。
定义 boolean dp[i][j] ,就表示字符串 s 的第i个字符和第j个字符之间是否为回文串,若是,再与最大长度比较、更新即可,同时记录i,j的下标。

代码

class Solution {
    public String longestPalindrome(String s) {
        int maxLen = 0;
        int start = 0, end = 0;
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int j = 0; j < s.length(); j++) {// j 取 j + 1作为结尾
            for (int i = j; i >= 0; i--) {
                int len = j - i + 1;//子串长度
                dp[i][j] = (len == 1 || len == 2 || dp[i + 1][j - 1]) && s.charAt(i) == s.charAt(j);
                if (dp[i][j] && len > maxLen) {
                    start = i;
                    end = j + 1;
                    maxLen = len;
                }
            }
        }
        return s.substring(start, end);
    }
}

需要注意的是:以j为结尾,i为开头,考虑i到j的子串时,根据上述递推可有:

dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j);

因为长度是1 和 2 的子串比较特殊,可以把 len == 1 和 len == 2 与dp[i + 1][j - 1] 取'||'关系整合到一起。另外,根据递推公式,子串的开头i要用到i + 1 的元素,所以要把 i 逆序遍历。

中心扩展法

核心思路

其实根据回文串的定义,不难想到,只要遍历每个字符,然后将该字符向两边扩展即可,每扩展一个相等的字符,就扩展一次左右长度,直到到达边界或者字符不相等结束即可。扩展函数如下:end - start - 1 这个返回值需要考虑

public int extand(String s, int start, int end){
        while(start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)){
            start--;
            end++;
        }
        return end - start - 1;
}

有了扩展函数,还要考虑一个回文串的特殊情况:奇数长度回文串和偶数长度回文串情况不同,需要两种情况都考虑,并取最大值留下。

代码

class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0) return "";
        int maxLen = 0;
        int start = 0, end = 0;
        for(int i = 0; i < s.length(); i++){
            int odd = extand(s, i, i);//奇数串
            int even = extand(s, i, i+1);//偶数串
            int temp = Math.max(odd, even);//取较大的那个回文串长度
            if(temp > maxLen){
                maxLen = temp;
                start = i - (maxLen - 1) / 2;//标记开始位置
                end = i + maxLen / 2;//标记结束位置
            }
        }
        return s.substring(start, end + 1);
    }

    public int extand(String s, int start, int end){
        while(start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)){
            start--;
            end++;
        }
        return end - start - 1;
    }
}

取开始和结束位置的公式可能不太好理解,分奇数偶数模拟一遍可以理解。

马拉车(Manacher)算法

终于到了重头戏了,这里特别感谢以下大佬的博客,帮助我理解了马拉车算法:程序员小川windliang百度百科,确实是前后参考、钻研了几个小时才彻底看明白,希望总结的这篇文章可以帮助到读者。

核心思路

首先要提一点,我接下来的讲解并不是直接给出马拉车算法的所有处理,而是一步步引导,我个人比较倾向于这种方式,感觉更好理解一点,废话不多说直接开始。
马拉车算法是专门来解决最长回文串问题的,它成功的将求最长回文串的复杂度降低到了O(n),当然这个算法也额外使用了O(n)的空间复杂度(一个Len[]数组)。马拉车算法最核心的思想就是重用,因为回文串具有对称性,那么只要能重用先前计算过的结果,就能大大的降低时间复杂度,详细思路我们一点一点展开,先知道这么个大概即可。

预处理

通过前边的几种解法,回文串在遇到奇数回文串和偶数回文串分开考虑比较麻烦,所以这里马拉车算法提供了一种思路:将原串每个字符前后都用 ‘#’ 插入其中,保证字符串的长度均为奇数


为什么转化为奇数呢?因为奇数串最中间的字符可以当做对称轴,方便操作,而偶数串最中间是两个字符之间,不是很方便(当然主要是为了统一,使得不同的串可以用相同的方法来判断)。另外,利用 奇数 + 偶数 = 奇数,#号个数比原字符串个数多一个,很容易得到每个新生成的子串均为奇数长度。我们令新生成的串赋值给 t。(ps:很多讲解马拉车算法的文章都会预处理时在现在t的基础上头尾分别添加一个 '^'和'$',我们后边用到再讲解,暂时先这样预处理就够用了)

辅助数组 Len[]

前边提到算法要额外使用Len数组,我们先给出该数组的定义:Len[i] 表示以 i 为中心的回文串开头到中心的长度(或中心到结尾的长度),包含中心字符。我们暂且称之为回文串的半径,得到关系如下图:

可以看到,Len[5]最大,其所对应的回文串也最长,同样,我们能看到对于整个回文串 #b#a#b#a#b#,Len[i] 和 i关于Len[5] 的对称元素 Len[i_symmetry]相等,例如:len[1] == len[9], len[3] == len[7]……还记得最开始提到马拉车算法就是利用回文串的对称性,重用先前的计算结果吗,现在我们找到的Len[i] 和 Len[i_symmetry]似乎就是可以重用的地方,可是真的只是怎么简单吗?我们来看下边的例子:
同样看Len[5],关于他对称的Len[3]和Len[7]是不相等的,为什么呢?
不同的颜色表示不同的回文串,可以看到对于Len[5],虽然Len[3] 和 Len[7] 关于他对称,但是以Len[3]为中心的回文串左端到头了,而以Len[7]为中心的回文串后边还有字符(图中红线划分的位置),所以,Len[7]不一定等于Len[3],但是,Len[7] >= Len[3],可以先令Len[7] = Len[3] 然后继续将7为中心的回文串向两端扩展。我们可以按下图分类计算出Len数组:
为了将两种情况合并在一起,我们可以将 Len[i] 取Right - i的右边界 和 Len[i_symmetry]的最小值,然后再向两边扩展 即:

            int i_symmetry = 2 * lastCenter - i;// i关于lastCenter的对称点
            if (i < lastRight) {
                // 可避免重复计算
                len[i] = Math.min(len[i_symmetry], lastRight - i);
            } else {
                // 需要中心扩展
                len[i] = 0;
            }

            while (i - len[i] >= 0 && i + len[i] < t.length() && t.charAt(i - len[i]) == t.charAt(i + len[i])) {
                len[i]++;
            }

求对称点的部分,根据对称思想可以知道: i + i_symmetry = 2 * Center; 所以就有了代码中的 i_symmetry 的求法。另外,代码中的else部分可以省略(默认值为0),只是为了方便理解。然后可能又会有疑问:为什么用lastCenter,和lastRight ?这是因为一个Center在从头开始遍历的时候是无法直接包括住整个数组的,所以我们存储前边计算过的较大长度的Center和Right,不断的更新即可。
那么,更新的时机应该满足什么条件呢?我们是不是能在以i为中心的回文串右边界超出lastRight时更新呢?似乎i后边的元素对应的回文串仍然可能在原来的Center包括的范围里,不过由于i对应回文串已经超过Center包括的范围,那么后边元素如果在Center的范围里的话也肯定在i的范围里,所以我们就找到了可以更新的条件了。

            if (lastRight < len[i] + i) {
                lastRight = len[i] + i;
                lastCenter = i;
            }

由于len[i]表示的是半径,所以用len[i] + i 就可以表示以i为中心回文串的右边界。这样我们就成功计算出了len数组的值,只要遍历过程中或者重新遍历一次找到最大的len值和下标就可以知道在预处理过后的数组的位置和长度了。

        int maxLen = 0;
        int center = 0;
        for (int i = 0; i < t.length(); i++) {
            if (maxLen < len[i]) {
                maxLen = len[i];
                center = i;
            }
        }

下标转换

有了len数组,但是len给出的maxLen 和 center 都是预处理过后的字符串,我们还需要转换为原字符串的下标和长度,长度比较简单,我们先来考虑长度。

长度

我们的预处理将每个字符前后都添加了一个'#',所以添加的'#'的个数就应该比原回文串的长度多一,又因为我们通过len数组的值(半径)可以计算出预处理后的回文串的长度:2 * len[i] - 1,所以原回文串的长度就可以计算为:(2 * len[i] - 1 - 1) / 2 = len[i] - 1;这样就得到了最长回文串的长度,maxLen = len[i] - 1

下标

首先我们先看下边例子的下标对应关系:

很恰巧,原数组的下标 i_pre = (i - 1 ) / 2; 所以我们有了上边的 maxLen 和 center 很容易就可以得到下标的转换并以此来求的最长回文字符串的起始下标:

int start = (center - maxLen) / 2;//(center - 1) / 2 - (maxLen - 1) / 2;
return s.substring(start, start + maxLen);

至此,我们已经可以解决这个问题了。不过还记得我在预处理部分说查到的很多讲解预处理过程都要在首尾加一个非'#'的字符吗?为什么我这里没用就实现了呢?我们先来看详细代码,然后分析原因。

完整代码
class Solution {
    //预处理
    public String preProcess(String s) {
        String t = "";
        for (int i = 0; i < s.length(); i++) {
            t += "#" + s.charAt(i);
        }
        return t + "#";
    }

    public String longestPalindrome(String s) {
        if (s.length() < 2)
            return s;
        String t = preProcess(s);
        int lastCenter = 0, lastRight = 0;// 存储上一个较大的回文串的中心和右边界
        int[] len = new int[t.length()];//存储半径的辅助数组
        for (int i = 0; i < t.length(); i++) {
            int i_symmetry = 2 * lastCenter - i;// i关于lastCenter的对称点
            if (i < lastRight) {
                // 可避免重复计算
                len[i] = Math.min(len[i_symmetry], lastRight - i);
            } else {
                // 需要中心扩展
                len[i] = 0;
            }

            while (i - len[i] >= 0 && i + len[i] < t.length() && t.charAt(i - len[i]) == t.charAt(i + len[i])) {
                len[i]++;
            }
            if (lastRight < len[i] + i) {
                lastRight = len[i] + i;
                lastCenter = i;
            }
        }

        int maxLen = 0;
        int center = 0;
        for (int i = 0; i < t.length(); i++) {
            if (maxLen < len[i] - 1) {
                maxLen = len[i] - 1;
                center = i;
            }
        }
        int start = (center - maxLen) / 2 ;
        return s.substring(start, start + maxLen);

    }
}
分析

由于我没有找到原Manacher前辈的论文,无法得证为什么需要在首尾额外加'$'或者'^',不过可以通过网上的博客分析个大概。首先,也是我觉得最靠谱的原因,在这行代码我使用了额外的判断来保证扩展在字符串的范围之内:

            while (i - len[i] >= 0 && i + len[i] < t.length() && t.charAt(i - len[i]) == t.charAt(i + len[i])) {
                len[i]++;
            }

而使用其他预处理之后因为在首尾各加入一个字符,且保证这两个字符不一样,这样如果判断到边界就肯定会直接跳出循环,不会越界:

            while(t.charAt(i - len[i]) == t.charAt(i + len[i])){
                len[i]++;
            }

这样就简化了判断条件。
还有另外一种原因,在遍历找最大长度时,直接使用 len[i] 而不使用len[i] - 1,在这种情况下,下标转换时 (center - maxLen) 会出现小于0的情况,所以在字符串最开头添加一个字符 '$' 来保证 (center - maxLen) 合法,不过这种说法实在有点牵强。总之,直接加'#'预处理和额外加首尾字符预处理的差别不是太大,注意细节即可,最重要的还是理解算法 len数组的计算和使用方法以及下标的转换 即可,最后的最后,附上添加额外首尾字符的预处理代码:

class Solution {

    public String preProcess(String s) {
        String t = "$";
        for (int i = 0; i < s.length(); i++) {
            t += "#" + s.charAt(i);
        }
        return t + "#^";
    }

    public String longestPalindrome(String s) {
        if (s.length() < 2)
            return s;
        String t = preProcess(s);
        int lastCenter = 0, lastRight = 0;// 存储上一个较大的回文串的中心和右边界
        int[] len = new int[t.length()];
        for (int i = 1; i < t.length() - 1; i++) {
            int i_symmetry = 2 * lastCenter - i;// i关于lastCenter的对称点
            if (i < lastRight) {
                // 可避免重复计算
                len[i] = Math.min(len[i_symmetry], lastRight - i);
            } else {
                // 需要中心扩展
                len[i] = 0;
            }

            while (t.charAt(i - len[i]) == t.charAt(i + len[i])) {
                len[i]++;
            }
            if (lastRight < len[i] + i) {
                lastRight = len[i] + i;
                lastCenter = i;
            }
        }

        int maxLen = 0;
        int center = 0;
        for (int i = 0; i < t.length(); i++) {
            if (maxLen < len[i]) {
                maxLen = len[i];
                center = i;
            }
        }
        int start = (center - maxLen) / 2 ;
        return s.substring(start, start + maxLen - 1);

    }
}

真的是挺难理解的算法,也是写了好长,如果有幸您能读到这里,希望你已经能理解马拉车算法,有问题或者文章的错误还请指出~感恩相遇


加油吧~为了未来
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 212,185评论 6 493
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,445评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,684评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,564评论 1 284
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,681评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,874评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,025评论 3 408
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,761评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,217评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,545评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,694评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,351评论 4 332
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,988评论 3 315
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,778评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,007评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,427评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,580评论 2 349

推荐阅读更多精彩内容