AcWing 1524. 最长回文子串
原题链接
简单
作者:
明日梦
,
2024-03-06 15:47:16
,
所有人可见
,
阅读 19
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
string s;
getline(cin, s);
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0)); // 初始化 dp 数组
int ans = 0; // 初始化答案
// 遍历所有可能的子串,更新 dp 数组
for (int len = 1; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (len == 1) {
dp[i][j] = 1; // 单个字符一定是回文子串
} else if (len == 2) {
dp[i][j] = (s[i] == s[j]); // 两个字符相同则为回文子串
} else {
dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]); // 更新回文子串状态
}
if (dp[i][j]) {
ans = max(ans, len); // 更新最长回文子串的长度
}
}
}
cout << ans << endl; // 输出结果
return 0;
}
大佬的区间dp 太棒了!