前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >最长回文子串——马拉车算法

最长回文子串——马拉车算法

作者头像
健程之道
发布2020-03-11 11:01:14
7610
发布2020-03-11 11:01:14
举报
文章被收录于专栏:健程之道

针对最长回文子串相关的问题,马拉车算法应该是比较通用的解法,今天我们就来具体看看这个算法。

简介

马拉车算法(Manacher‘s Algorithm)是用来查找一个字符串的最长回文子串的线性方法,由一个叫 Manacher 的人在1975年发明的,这个方法的最大贡献是在于将时间复杂度提升到了线性。

这个算法最厉害的地方是在于能够在线性时间内解决问题。一般我们解决最长回文子串,不可避免都要进行回溯之类的操作,那么时间复杂度一定是大于线性的。

而马拉车算法的主要思路是维护一个跟原字符串 str 长度一样的数组 lens,lens[i] 表示以 str[i] 为中点的回串其中一边的长度。

在这里,有的人把中点算进去,有的人记录两边的长度,其实都是一样的。我在这里是只记录一边的长度,不包括中点。比如CDCDE

代码语言:javascript
复制
str:  [C, D, C, D, E]
lens: [0, 1, 1, 0, 0]

那么 lens 里最大的自然就对应最长回串的中点了。所以这个算法的核心就是如何快速计算 lens。

具体思路

预处理

回文有奇偶长度两种情况,通过补充间隔符可以将这两种情况化简为奇数长度。

比如:

ABA补充为^#A#B#A#$,中点还是 B。 ABBA补充为^#A#B#B#A#$,中点为 #,最后可以去掉。

针对间隔符,首先要确保在字符串中不会出现,这里我是确保字符串中不会出现^、#、$

原字符串中每一个字符都会被#包围,这样就确保现在的字符串长度一定是奇数。

至于在开头增加^,在结尾增加$,这样是为了确保从任意一个位置开始检查回文时,一定会遇到不一样的时候,从而退出循环。而且也方便我们计算原字符的下标,直接除以2即可。

写法是:

代码语言:javascript
复制
        String str = "cbcbccde";
        char[] T = new char[str.length() * 2 + 3];
        T[0] = '^';
        T[1] = '#';
        T[T.length - 1] = '$';
        for (int i = 0; i < str.length(); i++) {
            char charStr = str.charAt(i);
            T[2 * i + 2] = charStr;
            T[2 * i + 3] = '#';
        }

计算长度数组

这就是算法的关键了,它充分利用了回文串的对称性。

我们用 C 表示回文串的中心,用 R 表示回文串的右边半径。所以 R = C + P[ i ] 。C 和 R 所对应的回文串是当前循环中 R 最靠右的回文串。用 i_mirror 表示当前需要求的第 i 个字符关于 C 对应的下标。

让我们考虑求 P [ i ] 的时候:

我们可以利用回文串 C 的对称性。i 关于 C 的对称点是 i_mirror ,P [ i_mirror ] = 3,所以 P [ i ] 也等于 3 。

但需要考虑特殊情况:

P [ i_mirror ] + i >= R

如下图:

当我们要求 P [ i ] 的时候,P [ mirror ] = 7,而此时 P [ i ] 并不等于 7 ,为什么呢,因为我们从 i 开始往后数 7 个,等于 22 ,已经超过了最右的 R ,此时不能利用对称性了,但我们一定可以扩展到 R 的,所以 P [ i ] 至少等于 R - i = 20 - 15 = 5,会不会更大呢,我们只需要比较 T [ R+1 ] 和 T [ R+1 ]关于 i 的对称点就行了,就像中心扩展法一样一个个扩展。

i_mirror - P [ i_mirror ] == 0

如下图:

此时P [ i_mirror ] = 1,但是 P [ i ] 赋值成 1 是不正确的,出现这种情况的原因是 P [ i_mirror ] 在扩展的时候首先是 "#" == "#" ,之后遇到了 "^"和另一个字符比较,也就是到了边界,才终止循环的。而 P [ i ] 并没有遇到边界,所以我们可以继续通过中心扩展法一步一步向两边扩展就行了。

C 和 R 的更新

既然知道如何计算长度数组了,那最关键的 C 和 R 到底什么时候需要更新呢?

i + P [ i ] > R时,也就是当求出的 P [ i ] 的右边界大于当前的 R 时,我们就需要更新 C 和 R 为当前的回文串了。因为我们必须保证 i 在 R 里面,所以一旦有更右边的 R 就要更新 R。

最终写法

假设我们要写一个方法,传入参数是原字符串s,返回值是各个字符对应的最长回文子串长度数组,那么具体方法就是:

代码语言:javascript
复制
    public int[] calSubstrings(String s) {
        if (s.length() == 0) {
            return new int[0];
        }
        // 存放新的内容
        char[] content = new char[s.length() * 2 + 3];
        // 开头用^
        content[0] = '^';
        // s中的每一个字符要用#包围
        content[1] = '#';
        for (int i = 0; i < s.length(); i++) {
            content[i * 2 + 2] = s.charAt(i);
            content[i * 2 + 3] = '#';
        }
        // 结尾用$
        content[content.length - 1] = '$';

        // 当前的回文串中心下标
        int center = 0;
        // 当前的回文串右边界
        int right = 0;
        // 存储以每一个位置为中心,所能获得的最长回文子串的长度
        int[] maxLength = new int[content.length];
        // 首尾两个字符没有必要计算
        for (int index = 1; index < content.length - 1; index++) {
            // 如果当前求解的位置,在右边界以内
            if (index < right) {
                // 则其最长回文子串的长度,至少为:
                maxLength[index] = Math.min(
                        // 对称center的位置上的
                        maxLength[center * 2 - index],
                        // 或者当前位置到右边界的距离
                        right - index
                );
            }

            // 正常求解,向左右扩展
            while (content[index + (maxLength[index] + 1)] ==
                    content[index - (maxLength[index] + 1)]) {
                maxLength[index]++;
            }

            // 如果当前index对应的右边界,比现有的right大
            if (index + maxLength[index] > right) {
                // 更新右边界和中心
                right = index + maxLength[index];
                center = index;
            }
        }

        // 最终的结果
        int[] result = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            result[i] = maxLength[i * 2 + 2];
        }
        return result;
    }

总结

以上就是我关于马拉车算法的理解,用来解决最长回文子串的问题,简直就是一把利器。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-03-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 健程之道 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 简介
  • 具体思路
    • 预处理
      • 计算长度数组
        • P [ i_mirror ] + i >= R
        • i_mirror - P [ i_mirror ] == 0
        • C 和 R 的更新
      • 最终写法
      • 总结
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档