题解 | #最长回文子串#

1 dp解法

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    string str;
    cin >> str;

    vector<vector<int>> dp(str.size(), vector<int>(str.size(), 0));
    int result = 1;
    for (int i = 0; i < str.size(); ++i) {
        dp[i][i] = 1;
    }

    for (int i = str.size() - 2; i >= 0; --i) {
        for (int j = i + 1; j < str.size(); ++j) {
            if (j - i == 1) {
                if (str[i] == str[j]) {
                    dp[i][j] = 1;
                    result = max(result, j - i + 1);
                }
                else dp[i][j] = 0;
            }
            else {
                if (str[i] == str[j]) {
                    dp[i][j] = dp[i + 1][j - 1];
                    if (dp[i][j]) result = max(result, j - i + 1);
                }
                else dp[i][j] = 0;
            }
        }
    }

    cout << result << endl;
}
// 64 位输出请用 printf("%lld")

2 双指针解法

int getLen(const string& str, int low, int high) {
    while (low >= 0 && high < str.size() && str[low] == str[high]) {
        --low;
        ++high;
    }
    return high - low - 1;
}

int main() {
    string str;
    cin >> str;

    int result = 1;
    for (int i = 0; i < str.size() - 1; ++i) {
        int len1 = getLen(str, i, i);
        int len2 = getLen(str, i, i + 1);
        result = max(result, max(len1, len2));
    }

    cout << result;
}