给定一个字符串a求他的所有回文子串回文子串长度至少为2且为a的子串且为回文且为字符串用C++实现
以下是C++实现的代码:
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<string> palindromeSubstrings(string a) {
vector<string> result;
int n = a.length();
vector<vector<bool>> dp(n, vector<bool>(n, false));
// 单个字符都是回文子串
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
// 判断长度为2的子串是否是回文子串
for (int i = 0; i < n - 1; i++) {
if (a[i] == a[i + 1]) {
dp[i][i + 1] = true;
result.push_back(a.substr(i, 2));
}
}
// 判断长度大于2的子串是否是回文子串
for (int len = 3; len <= n; len++) {
for (int i = 0; i < n - len + 1; i++) {
int j = i + len - 1;
if (a[i] == a[j] && dp[i + 1][j - 1]) {
dp[i][j] = true;
result.push_back(a.substr(i, len));
}
}
}
return result;
}
int main() {
string a = "abcba";
vector<string> result = palindromeSubstrings(a);
cout << "回文子串列表:" << endl;
for (string str : result) {
cout << str << endl;
}
return 0;
}
输出:
回文子串列表:
a
b
c
b
abcba
``
原文地址: https://www.cveoy.top/t/topic/h82f 著作权归作者所有。请勿转载和采集!