@keddad
Ученик

Как восстановить ответ при вычислении максимального подпалиндрома с помощью ДП?

Задача: поиск максимального подпалиндрома. Я иду динамикой, между строкой x и строкой, обратной x для поиска длинны максимального подпалиндрома:
Код для вычисления
#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;
        }
    }

Потом просто реверся строку answ. Но мой метод восстановления не работает, хотя, по сути, это полный реверс самой динамики. Что я делаю не так?
  • Вопрос задан
  • 84 просмотра
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы