1040. Longest Symmetric String.md

pat 甲级 1040. Longest Symmetric String

题意概述

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

输入输出格式

输入一个字符串。

输出字符串中的最长回文子串长度。

数据规模

字符串长度不超过 1000。

算法设计

求解最长回文子串问题是一个经典问题，解决它的算法有很多：

1. 暴力算法：枚举所有子串的两个端点，再判断这个子串是否是回文串。时间复杂度为$O(n^3)。
2. 中心扩展算法：枚举所有的回文中心并尝试不断向两端扩展，直到无法扩展为止，此时的回文串长度即为此回文中心下的最长回文串长度。时间复杂度为$O(n^2)$。
3. 动态规划算法：如果一个字符串是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串，这样就可以进行状态转移，使用动态规划进行求解。时间复杂度为$O(n^2)$。
4. Manacher 算法。该算法非常复杂，但可以用$O(n)$的时间复杂度求解该问题。

每类算法的具体讲解可参考力扣——最长回文子串。

下面讨论最容易理解的中心扩展算法。

遍历输入的字符串，以遍历到的当前字符为回文中心，不断向字符串两端延伸通过判断两侧字符是否相同即可得出以此字符为中心的最长回文子串，显然，这种回文子串长度一定是奇数。考虑长度为偶数的回文子串，以遍历到的当前字符为回文中心左侧字符，以当前字符的下一个字符为回文中心右侧字符，不断向字符串两端延伸通过判断两侧字符是否相同即可得出以此字符为回文中心左侧字符的最长回文子串。在上述遍历过程中，不断更新回文子串的最大长度，最后输出即可。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    getline(cin, s);
    gg ans = 0;
    for (gg i = 0; i < s.size(); ++i) {
        for (gg j = 0; i - j >= 0 and i + j < s.size() and s[i - j] == s[i + j]; ++j) {
            ans = max(ans, 1 + 2 * j);
        }
        for (gg j = 0; i - j >= 0 and i + j + 1 < s.size() and s[i - j] == s[i + j + 1]; ++j) {
            ans = max(ans, 2 * j + 2);
        }
    }
    cout << ans;
    return 0;
}