Luobuyu's Blog

0%

5. 最长回文子串

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 2.6k 阅读时长 ≈ 2 分钟
经典最长回文子串。

5.最长回文子串

题目描述：

给定一个字符串s，找出s中的最长回文串。

数据范围：

$1\le n \le 1000$

题解：

马拉车算法（Manacher）：

image-20230525110900629

image-20230525110930007

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
int p[maxn * 2];
void manacher(const char *t, int n)
{
    static char s[maxn * 2];
    int l = 0;
    s[l++] = '$';
    s[l++] = '#';
    for (int i = 0; i < n; ++i)
    {
        s[l++] = t[i];
        s[l++] = '#';
    }
    s[l] = '\0';
    int mx = 0, j = 0;
    for (int i = 1; i < l; ++i) // 因为0是$，从1开始
    {
        p[i] = (mx > i ? min(p[j * 2 - i], mx - i) : 1);
        // 还要判断是否合法
        while (i - p[i] != 0 && i + p[i] != l && s[i - p[i]] == s[i + p[i]])
            p[i]++;
        if (i + p[i] > mx)
        {
            mx = i + p[i];
            j = i;
        }
    }
}

马拉车算法求出来的臂长数组是每个元素作为中心点，回文串的半径。为了统一奇数和偶数长度字符串，做过处理，加入了#字符。如 aaba变成了 #a#a#b#a#，奇数长度加入了偶数个#，偶数长度加入了奇数个#，最后字符串的长度为奇数。返回的半径数组 $p[i]$ 包括了#，并且包含了中心点。

s#a#a#b#a#
$p[i]$123214121
$p[i] - 1$012103010

假设 $x = p[i] - 1$ ，即 $x$ 为不含中心点的半径长度，则 $len = (x-1) / 2 \times 2 + 1$ ，因为去除中心点之后，变成了 #……#，减一之后变成了 #a#a……a，这时#和字母是一对一的，所以除以 $2$ 得到真实的去除中心点半径，然后乘以 $2$ 得到回文串长度，最后加上中心点。

也可以假设 $x = p[i]$ ，即 $x$ 为含中心点的半径长度，则 $len = x / 2 \times 2 - 1 = x - 1$ 。因为包含中心点已经是#和字母一对一的了，然后 $/2 \times 2$ 得到总长度，但是中心点算了两次，因此最后减去 $1$ 。

$p[i] - 1$ 就是回文串的长度。中心点为 $i$ ，则可以得到起点为 $i - (p[i]-1)/2$ 。

中心扩展算法：

从每一个位置出发，向两边扩展，因为长度有偶数有奇数，所以从每一个位置出发时也要考虑位置 $i,i$ ，位置 $i,i+1$ 。向两边扩展直到遇到不相等的，记录答案。

代码：

马拉车 $O(n)$ ：

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
43
44
45
46
47
48
49
50
51
52
53
54
55
auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e3 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    int p[maxn * 2];
    void manacher(const char *t, int n)
    {
        static char s[maxn * 2];
        int l = 0;
        s[l++] = '$';
        s[l++] = '#';
        for (int i = 0; i < n; ++i)
        {
            s[l++] = t[i];
            s[l++] = '#';
        }
        s[l] = '\0';
        int mx = 0, j = 0;
        for (int i = 1; i < l; ++i)
        {
            p[i] = (mx > i ? min(p[j * 2 - i], mx - i) : 1);
            while (i - p[i] != -1 && i + p[i] != l && s[i - p[i]] == s[i + p[i]])
                p[i]++;
            if (i + p[i] > mx)
            {
                mx = i + p[i];
                j = i;
            }
        }
    }
    string longestPalindrome(string s)
    {
        int n = s.length();
        manacher(s.c_str(), n);
        int maxx = 0, index = -1;
        for (int i = 1; i < n * 2 + 2; ++i)
        {
            if (p[i] - 1 > maxx)
            {
                maxx = p[i] - 1;
                index = i / 2 - 1;
            }
        }
        return s.substr(index - (maxx - 1) / 2, maxx);
    }
};

中心扩展 $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
class Solution {
public:
    void expandAroundCenter(int& l, int& r, const string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            --left;
            ++right;
        }
        l = left + 1;
        r = right - 1;
    }

    string longestPalindrome(string s) {
        int start = 0, end = 0;
        int l, r;
        for (int i = 0; i < s.size(); ++i) {
            expandAroundCenter(l, r, s, i, i);
            if (r - l > end - start) {
                start = l;
                end = r;
            }
            expandAroundCenter(l ,r, s, i, i + 1);
            if (r - l > end - start) {
                start = l;
                end = r;
            }
        }
        return s.substr(start, end - start + 1);
    }
};