回文串实现--轻松理解Manacher算法

2021/7/10 20:10:09

本文主要是介绍回文串实现--轻松理解Manacher算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

首先说一下什么是回文串?

回文串就是一个字符串的逆序和正序相同,此字符串就是回文串。比如:abcdedc中的 cdedc就是会问串。那么回文串问题怎么解决呢?

前置操作:

因为回文串分为奇数串和偶数串,比如奇数串为:abcba这样是以c为中心向两边扩,直接遍历字符串就行了,但是如果遇到偶数串的时候直接遍历,判断两边字符是否相等就不行了,比如abba这样的字符,以两个b之间的位置作为中心,这样就需要添加辅助的字符,所以我们拿到字符串时,需要对字符串进行处理,把字符串的每个位置都插入其他字符,比如#a#b#b#a#这样我们直接遍历就行了,插入的辅助字符是否可以和已有字符相同呢?答案是:可以的,因为就算插入了辅助字符,还是已有字符和已有字符相比较,辅助字符和辅助字符相比较,所以是可以的。

方法一:朴素法

我们可以遍历每个字符串,然后向前向后分别扩充,最后得到最长的回文串。

时间复杂度为:O(n^2),空间复杂度为:O(1)代码实现如下:

public String longestPalindrome(String s) {
        StringBuilder sb = new StringBuilder("#");
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i)).append("#");
        }
        char[] chars = sb.toString().toCharArray();
        String maxStr = "";
        int max = 0;
        for (int i = 0; i < chars.length; i++) {
            int j = 1;
            while (i + j < chars.length && i - j >= 0 && chars[i - j] == chars[i + j]) {
                j++;
            }
            if (max < j) {
                max = j;
                maxStr = sb.substring(i - j + 1,i + j);
            }
        }
        return maxStr.replaceAll("#","");
    }

方法二:Manacher算法

此方法的好处是时间复杂度可以接近O(n),通过维护一个半径数组,可以实现加速匹配字符串。有一个R为最右边界,维护匹配字符的最右边的字符。还有一个中心位置C位,这个的作用为可以快速找到回文串L-C-R之间的所有位置的半径。

主要分为四种情况:

  1. 右边界小于遍历的字符下标,则需要暴力匹配下一个字符,然后更新R。
  2. 匹配的字符小于右边界,并且C左边对应的半径也小于最左边界,则直接使用左边的半径。比如abcbdedbcbaerft,e中C位R为a,遍历到第二个c位置时就可以直接拿到第一个c的半径,因为其半径在最左边界内部。
  3. 匹配的字符小于右边界,但是C左边对应的半径大于左边界,则可以直接把半径写成R-i,因为如果R+1的字符等于L-1的字符的话,则还可以扩,之所以没有扩,就说明不等于。
  4. 匹配的字符小于右边界,但C左边对应的半径等于右边界,这种情况则需要暴力扩展了。可以直接扩展R+1位置。

代码实现如下:

public String longestPalindrome(String s) {
        StringBuilder sb = new StringBuilder("#");
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i)).append("#");
        }
        char[] chars = sb.toString().toCharArray();
        int[] ids = new int[chars.length]; // 回文半径数组
        int C = -1; // 中心
        int R = -1; // 最右边界,最右边有效区域为R-1
        String maxStr = "";
        int max = 0;
        for (int i = 0; i < chars.length; i++) {
            // ids数组加速i的匹配速度,如果之前匹配过了,则越过直接匹配没有匹配过的。
            ids[i] = R > i ? Math.min(ids[2 * C - i],R - i) : 1;
            // 暴力匹配按字符匹配。
            while (ids[i] + i < chars.length && i - ids[i] > -1) {
                if (chars[ids[i] + i] == chars[i - ids[i]]) {
                    ids[i]++;
                } else {
                    break;
                }
            }
            // 如果遍历字符超过最右边界,则更新最右边界,及中心位置
            if (R < i) {
                R = i + ids[i];
                C = i;
            }
            if (max < ids[i]) {
                max = ids[i];
                maxStr = sb.substring(i - ids[i] + 1,i + ids[i]);
            }
        }

        return maxStr.replaceAll("#","");
    }

 通过这个半径数组可以解决很多字符串的相似问题,半径数组是Manacher算法的核心。



这篇关于回文串实现--轻松理解Manacher算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程