用c++ 语言给你一个字符串s,找到s中最长的回文子串
时间: 2024-02-26 22:57:43 浏览: 29
好的,我可以为您提供如下的C++代码实现:
```
#include <iostream>
#include <cstring>
using namespace std;
string longestPalindrome(string s) {
int n = s.size();
if(n < 2) return s;
bool dp[n][n];
memset(dp, false, sizeof(dp));
int start = 0, maxLen = 1;
for(int i = 0; i < n; i++) dp[i][i] = true;
for(int j = 1; j < n; j++) {
for(int i = 0; i < j; i++) {
if(s[i] == s[j]) {
if(j - i < 3) dp[i][j] = true;
else dp[i][j] = dp[i+1][j-1];
}
else dp[i][j] = false;
if(dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
start = i;
}
}
}
return s.substr(start, maxLen);
}
int main() {
string s = "babad";
string res = longestPalindrome(s);
cout << res << endl;
return 0;
}
```
这里使用了动态规划的思想,首先定义一个二维数组 `dp[i][j]` 表示字符串从 i 到 j 是否是回文串,初始时所有的 `dp[i][i]` 都为 true。接着从字符串长度小的子串向长度大的子串递推,判断当前的子串是否为回文串,如果是,则继续判断更长的子串是否为回文串。最后找到最长的回文子串的起始位置和长度,返回即可。