最长回文子串算法

发表于 分类于 ， 阅读次数： 本文字数： 1.9k 阅读时长 ≈ 7 分钟

leetcode5:https://leetcode-cn.com/problems/longest-palindromic-substring/description/
可以自己提交看看对不对

暴力搜索

这个应该是最容易的方法了，但是一看复杂度O(n3)，还是放弃好了。

但是这个方法也是遍历所有字符串字串的一种方法。下面是暴力搜索的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 暴力循环
public static String maxPalindromeStringForce(final String target) {
    if (target.length() == 0)
        return target;
    int maxLen = 1;
    int BeginIndex = 0;
    for (int i = 0; i < target.length(); i++) {
        for (int j = i + 1; j < target.length(); j++) {
            if (isPalindromeString(target.substring(i, j + 1)) && j - i + 1 > maxLen) {
                BeginIndex = i;
                maxLen = j - i + 1;
            }
        }
    }
    return target.substring(BeginIndex, BeginIndex + maxLen);
}

public static boolean isPalindromeString(final String target) {
    int l = 0;
    int r = target.length() - 1;
    while (l <= r) {
        if (target.charAt(l) != target.charAt(r)) {
            return false;
        }
        l++;
        r--;
    }
    return true;
}

中心拓展法

这个比暴力搜索复杂度要少一个数量级
为什么呢？它用到了回文串的一个特性左右对称
其实在暴力搜索的判断是否为回文串的时候我们已经用了这个特性了
但是我们是对每一段字串用这个特性即用它去判断而不是去获取
所以我们对每一个字符从中间向外展开以获取以此字符为中心的最长回文字串
这样外循环为字符串遍历 内循环为获得回文子串 复杂度最差意思就是O(n2)
但是有一个地方必须注意，中心拓展中心一词是相对于长度为奇数的串的，
对于偶数串我们要单独判断，方法也很简单看看该字符后一个字符是不是一样就行，代码里有解释
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 中心向外拓展
public static String maxPalindromeStringCenter(final String target) {
    if (target.length() == 0)
        return target; // 如果是空字符串则直接返回
    int beg = 0;
    int end = 0;
    for (int i = 0; i < target.length(); i++) {
        int l = i;
        int r = i;
        // 回文串是奇数
        while (target.charAt(l) == target.charAt(r)) {
            l--;
            r++;
            if (l == -1 || r == target.length())
                break;
        }
        l++;
        r--;
        if (r - l > end - beg) {
            beg = l;
            end = r;
        }
        // 回文串是偶数
        if (i < target.length() - 1 && target.charAt(i + 1) == target.charAt(i)) {
            r = i + 1;
            l = i;
            while (target.charAt(l) == target.charAt(r)) {
                l--;
                r++;
                if (l == -1 || r == target.length())
                    break;
            }
            l++;
            r--;
            if (r - l > end - beg) {
                beg = l;
                end = r;
            }
        }
    }
    return target.substring(beg, end + 1);
}

Dp动态规划

字符串类的题目怎么可能少了动态规划呢
那么状态该怎么转移呢

dp[i][j] = true ,if dp[i+1][j-1] == true && str[i]==str[j]
否则 dp[i][j] = false

至于为什么，因为我们在已经知道串[i,j]是回文字串的时候
只要 str[i-1] == str[j+1] 那么[i-1,j+1]也是一个回文子串
为了更好找到最长所以这里将微循环设置为长度循环，内循环为字串头地址
需要注意的是预处理，每个字母都是一个长度为1 的回文串
和中心拓展类似偶数串中心是两个相同的字母所以还要考虑相邻字母相同的情况
复杂度虽然和中心拓展一个数量级但是还是要比它快许多哦
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// Dp动态规划
public static String maxPalindromeStringDp(final String target) {
    if (target.length() == 0)
        return target;
    int len = target.length();
    if (len == 0)
        return target;
    int beginIndex = 0;
    int maxLen = 1;
    boolean[][] isPalindrom = new boolean[len][len];
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            isPalindrom[i][j] = false;
        }
    }
    for (int i = 0; i < len; i++) {
        isPalindrom[i][i] = true;
        if (i < len - 1 && target.charAt(i) == target.charAt(i + 1)) {
            isPalindrom[i][i + 1] = true;
            beginIndex = i;
            maxLen = 2;
        }
    }
    for (int strlen = 3; strlen <= len; strlen++) {
        for (int i = 0; i <= len - strlen; i++) {
            int end = i + strlen - 1; // 字串结束的位置
            if (isPalindrom[i + 1][end - 1] == true && target.charAt(i) == target.charAt(end)) {
                isPalindrom[i][end] = true;
                maxLen = strlen;
                beginIndex = i;
            }
        }
    }
    return target.substring(beginIndex, beginIndex + maxLen);
}

Manacher算法

很多人也许和我一样听到最长回文子串还有O(n)解法的时候是不相信的
但是事实就是如此，这个算法也叫马拉车算法（只是谐音哦）
我认为它也是一种动态规划思想 但是用的更加的巧妙
在某种程度上和KMP算法有异曲同工之处

1.统一格式化源字符串

不知道是否有人注意到了上面几种算法在某些方面都考虑奇数串和偶数串的情况
为了简化考虑情况设置一下规则：

\(abcd\rightarrow \#a\#b\#c\#d\#\)

这样所有的字符串就都是奇数串了

2.设置映射关系

我们需要的是源字符串啊
处理成那种乱七八糟的字符串，即使得到了结果还要将所有 # 取代
所以我们看看能不能找到新串和原串之间的关系
这样处理后表达一个回文串最好的方式就是中心mid（也就是为什么统一为奇数串的原因）和半径来表示r
在我们知道mid和r的时候怎么确定原串呢。
假设有串 #c#a#b#a# 原串是 caba
显而易见的是 aba 是回文串a在原串的下标是1
在新串中下标是5，也就是 mid = 5 , r = 4
乍一看就是 beginIndex = mid-r
但是 #a#b#a# 此时 mid = 3， r = 4 那么 beginIndex = -1
显然不对所以我们在最开始处加上一个与#不同的符号$，那么新串即是 $#a#b#a#
此时 mid = 4 r = 4 那就很符合了
但是对 #c#a#b#a# 又不符合了，所以我们找到了新的关系 beginIndex = (mid-r)/2 这是最符合的 感兴趣的小伙伴可以自己推一推

3.找到 mid 以及 r

p[i] = mostRight > i ? min(p[2 * mid - i], mostRight - i) : 1;
p[i] 为以i为中心的半径 mostRight是已知的回文串右端点最右的那个的下标 mid则是其中心
由于回文串的对称性 p[i] = min(p[2 * mid - i], mostRight - i) p[2*mid-i]是其对称中心点下标
他们两个在以mid为中心的回文串内对称部分相同也就是半径相同(一定注意是回文串内)
在外面的部分我们无从得知只能老老实实匹配 也就是置为1（自己就是回文串）

4.复杂度

因为每次循环内要不是用到以前的结论（对于的中心点）要么就是向右拓展
所以复杂度是O(n)
并不是有两个循环复杂度就是O(n2)

5.代码如下（其实先看代码可能更好理解）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// manacher
public static String maxPalindromeStringManacher(final String target) {
    if (target.length() == 0)
        return target;
    StringBuffer temp = new StringBuffer("$#");
    for (int i = 0; i < target.length(); i++) {
        temp.append(target.charAt(i) + "#");
    }
    // 防止$#a#b#a# 读到最后a的时候向两边扩散的时候溢出 C++则不需要C++字符串有/0结束符最后加的字符不能为$否则还是会溢出
    temp.append('&');
    int[] p = new int[temp.length() + 1]; //以i为中心的半径
    int mostRight = 0; // 已知回文串所能达到的最右边的下标
    int mid = 0; // 已知最右边的回文串的中心下标
    int resLen = 1;
    int resMid = 0;
    for (int i = 1; i < temp.length() - 1; i++) { // 注意是从1开始第一个字符不算在内
        // 最关键一步 初始化已知的 p[i]
        p[i] = mostRight > i ? Math.min(p[2 * mid - i], mostRight - i) : 1;
        while (temp.charAt(i + p[i]) == temp.charAt(i - p[i]))
            p[i]++;
        if (mostRight < i + p[i]) {
            mostRight = i + p[i];
            mid = i;
        }
        if (resLen < p[i]) {
            resLen = p[i];
            resMid = i;
        }
    }
    return target.substring((resMid - resLen) / 2, (resMid - resLen) / 2 + resLen - 1);
}

如果还有疑惑 可以参考下面两篇文章（我觉得很不错的）：
https://www.cnblogs.com/grandyang/p/4475985.html(我也是这里学习的) https://mp.weixin.qq.com/s/Zrj35DrnQKtAENiR5llrcw(漫画的形式讲的很清楚) 不好的地方 欢迎提出(￣▽￣)"