最长回文子串

题意

求字符串中最长的回文子串。

思路

枚举每个中心位置（奇数长度以字符为中心，偶数长度以间隙为中心），向两侧扩展直到不回文，记录最长。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size(), start = 0, len = 0;
        auto expand = [&](int l, int r) {
            while (l >= 0 && r < n && s[l] == s[r]) {
                l--;
                r++;
            }
            if (r - l - 1 > len) {
                start = l + 1;
                len = r - l - 1;
            }
        };
        for (int i = 0; i < n; i++) {
            expand(i, i);
            expand(i, i + 1);
        }
        return s.substr(start, len);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    cout << Solution().longestPalindrome(s) << '\n';
    return 0;
}

python

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#!/usr/bin/env python3
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        start = length = 0

        def expand(l, r):
            nonlocal start, length
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            if r - l - 1 > length:
                start = l + 1
                length = r - l - 1

        for i in range(n):
            expand(i, i)
            expand(i, i + 1)
        return s[start : start + length]


def main():
    print(Solution().longestPalindrome(input().strip()))


if __name__ == "__main__":
    main()

复杂度

时间复杂度： $O(n^2)$ 。
空间复杂度： $O(1)$ 。

总结

中心扩展是最直观的回文子串解法。Manacher 算法可优化到 $O(n)$ ，但中心扩展对 $n \leqslant 1000$ 足够。

目录

题意

思路

代码

复杂度

总结