algorithm

最长回文子串

本文讨论求解字符串最长回文子串长度和位置的方法。

最长回文子串

对于一个字符串，顺着读和反着读是一样的字符序列，则称其为回文串，即反转后的字符串和原字符串相同。给定一个字符串，判断其是否为回文串的方法很简单，至少我们可以给出两种显而易见的方法：

  • 反转当前字符串，判断是否和原字符串相同
  • 分别从字符串的头和尾开始，逐一判断是否两边的字符相同

倘若给定一个字符串，如何求其最长的回文子串？

朴素/暴力

根据回文串的长度奇偶性，回文串中心有一个字符或者两个字符，对于每个位置的字符，求出以其为中心的奇数长度的最长回文串长度，以及以其为偏中心的偶数长度的最长回文串长度，也可以求出字符串的最长回文子串。暂且称之为朴素算法或者暴力算法。

过程

从i等于0到n-1，枚举每一个位置，分别求以其为中心的最长奇数长度回文子串的长度以及以其为左中心的最长偶数长度回文子串的长度。我们先求这两种情况下的字符串半径长度，分别使用odd和even数组保存这两种值，比如，对于如下示例字符串，两个数组的取值情况：

string a b a d d
odd 1 2 1 1 1
even 0 0 0 1 0

对于回文子串”aba”其半径为2，中心位于i = 1，半径为2，因此odd[1] = 2；对于回文子串”dd”，左中心位于i = 3，半径为1，因此even[i] = 1。

对于odd数组，当索引为i时，显然单个字符构成的子串肯定回文，因此odd[i] >= 1，然后不断往两边延伸判断是否字符相等，递增odd[i]，当遇到不同的边界字符时停止。

对于even数组，当索引为i时，需要满足i < n - 1，因为i是偶数回文串的左中心，even[i] >= 0，我们从半径为0开始探测两边的字符是否相等，不断递增半径知道遇到两个不相等的字符。

实现

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
string violent(string str)
{
    int n = str.length();
    int odd[n];
    int even[n];

    for (int i = 0; i < n; ++i)
    {
        odd[i] = 1;
        while (i - odd[i] >= 0 && i + odd[i] < n
            && str[i - odd[i]] == str[i + odd[i]])
            ++odd[i];
        even[i] = 0;
        while (i - even[i]>= 0 && i + even[i] + 1 < n
            && str[i - even[i]] == str[i + even[i] + 1])
            ++even[i];
    }

    // case 1: in odd len = 2 * r - 1
    // case 2: in even len = 2 * r
    auto idx1 = max_element(odd, odd + n) - odd;
    auto idx2 = max_element(even, even + n) - even;
    if (odd[idx1] <= even[idx2])
        return str.substr(idx2 - even[idx2] + 1, 2 * even[idx2]);
    else
        return str.substr(idx1 - odd[idx1] + 1, 2 * odd[idx1] - 1);
}

动态规划

对于一个字符串str，假设从索引i到j的一段子串用σ(i, j)表示，则很容易联想到，如果σ(i + 1, j - 1)是一个回文子串，且str[i] = str[j]，则σ(i, j)也是一个回文子串（暂时不考虑边界问题，如i+1是否大于j-1），这已经是一个最优子结构了，因此我们可以通过动态规划，不断枚举子串的长度，求出一个表格，包含所有子串是否是回文子串的信息。

使用dp[i][j]表示σ(i, j)是否是一个合法回文子串，n为字符串str长度：

  • 单个字符构成一个合法的回文子串，即dp[i][i] = true(0 <= i < n)
  • 双字符如果相同则也构成一个合法回文子串，即如果str[i] = str[i+1]，则dp[i][i+1] = true(0 < i < n - 1)
  • 对于长度大于2的子串σ(i, j)，dp[i][j] = dp[i+1][j-1] && str[i] == str[j]

实现

c++程序如下，时间复杂度为O(n^2)：

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
string longestPalindrome(string str) {
    size_t n = str.length();
    bool dp[n][n];
    memset(dp, 0, sizeof(dp));

    size_t ans = 1;
    size_t idx = 0;

    for (size_t i = 0; i < n; ++i)
    {
        // case 1: 单个字符可以组成一个回文子串
        dp[i][i] = true;

        // case 2: 双字符如果相同，可以组成一个回文子串
        if (i != n - 1 && str[i] == str[i+1])
        {
            dp[i][i+1] = true;
            ans = 2;
            idx = i;
        }
    }

    for (size_t l = 3; l <= n; ++l)
    {
        for (size_t i = 0; i < n - l + 1; ++i)
        {
            size_t j = i + l - 1;
            dp[i][j] = (dp[i + 1][j - 1] && str[i] == str[j]);
            if (dp[i][j])
            {
                ans = l;
                idx = i;
            }
        }
    }

    return str.substr(idx, ans);
}

Manacher

我们考虑一个例子：string = “abaacaabaefg”，按照朴素思想，枚举索引从i = 0到i = 4，显然最长的回文子串是起始处的”abaacaaba”，当我们枚举i = 5时，i落在下标为4，半径为5的子串中，因此i关于4的对称位置为3，而下标为3的最大回文子串半径我们已经求得了，i = 5时的最大回文子串肯定不小于i = 3时最大回文子串的半径。因此通过维护一个当前已知的最右边的边界，我们可以判断是否目前枚举的下标，在某个已经求出最大半径的回文子串范围中，通过对称关系，我们可以直接获取当前索引出最长回文子串的最大半径至少是多少，而不用从0开始暴力，同时，我们需要维持目前最右边界。

过程

实现

根据上一节的描述，c++实现算法如下：

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
string manacher(string str)
{
    string estr;
    size_t n = str.length();
    estr.reserve(n * 2 + 1);

    estr += "^#";
    for (size_t i = 0; i < n - 1; ++i)
    {
        estr += str[i];
        estr += '#';
    }
    estr += str.back();
    estr += "#$";

    n = estr.length();
    size_t dp[n];
    size_t mid = 0;
    dp[0] = 1;

    for (size_t i = 1; i < n; ++i)
    {
        dp[i] = i < mid + dp[mid] ?  dp[2 * mid - i] : 1;

        while (estr[i + dp[i]] == estr[i - dp[i]])
            ++dp[i];
        if (mid + dp[mid] < i + dp[i])
            mid = i;
    }

    auto iter = max_element(dp, dp + n);
    size_t len = *iter;
    size_t idx = iter - dp;
    len /= 2;
    idx = idx / 2 - 1;
    idx -= len - 1;

    return str.substr(idx, 2 * len - 1);
}

复杂度分析

根据最右边界所属子串的中心的更新，即mid，可以估算复杂度。

  • 首先，mid的值根据i更新，因此mid不会超过i，即总可以找到一个镜像j，其和i关于mid对称，且j < mid < i。

  • 如果i加上镜像j的半径dp[j]没有超过最有边界，即i + dp[j] - 1 < mid + dp[mid] - 1，此时以j为中心的最长回文子串完全位于mid为中心的子串中，i为中心的回文子串不可能再扩展，dp[i] = dp[j]

  • 如果上述情况下，i + dp[j] - 1 = mid + dp[mid] - 1，此时最右边的一个字符也是dp[i]当前可以探测到的回文子串最右边的字符，此时是有可能继续往右扩展的，例如”cbabcb”，i = 4，mid = 2时，j = 0，此时i可以继续往右扩展字符，探测到b，组成回文串”bcb”

因此，该算法的复杂度即最有边界不断往右移动的复杂度O(n)。