Answer the question
In order to leave comments, you need to log in
How to recover the answer when calculating the maximum subpalindrome using DP?
Task: find the maximum subpalindrome. I go dynamically between the string x and the reverse of x to find the length of the maximum subpalindrome:
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main() {
string s1, s2;
cin >> s1;
s1 = " " + s1;
s2 = s1 + " ";
reverse(s2.begin(), s2.end());
vector<vector<int>> d(s1.length(), vector<int>(s2.length(), 0));
for (int i = 1; i < d.size(); ++i) {
for (int j = 1; j < d[i].size(); ++j) {
if (s1[i] == s2[j]) {
d[i][j] = ++d[i - 1][j - 1];
} else {
d[i][j] = max(d[i - 1][j], d[i][j - 1]);
}
}
}
cout << d.back().back();
}
string amsw;
int i = s1.size() - 1, j = s1.size() - 1;
while (true) {
if( i == 0 or j == 0){
break;
}
if (d[i][j] == d[i - 1][j - 1] + 1) {
amsw.push_back(s1[i]);
--i; --j;
}
else if(d[i][j] == d[i-1][j]){
--i;
} else {
--j;
}
}
Answer the question
In order to leave comments, you need to log in
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question