2

Пытался на днях решить задачу поиска наибольшей общей подпоследовательности в строке. Получилось, но не совсем.

Само ДП, полагаю, решено верно. А вот раскрутка на получение ответа, видимо нет. На некоторых тестах возвращает строку не полностью, а с обрезанным началом.

Привожу код и тест:

Код:

#include <bits/stdc++.h>
using namespace std;

///HI THERE ;)
int main(int argc, char **argv) {

string s1, s2;
getline(cin, s1); //s1 = "X" + s1;
getline(cin, s2); //s2 = "X" + s2;

swap(s1, s2);

vector<vector<int> > f(s1.size() + 1, vector<int>(s2.size() + 1, 0));

for(int i = 1; i <= s1.size(); i++) {
    for(int j = 1; j <= s2.size(); j++) {
        if(s1[i] == s2[j]) f[i][j] = f[i - 1][j - 1] + 1;
        else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
    }
}

int i = s1.size(), j = s2.size();
string ans;

while(i != 0 && j != 0) {
    if(s1[i] == s2[j]) {
        ans += s1[i];
        i--, j--;
    } else {
        if(f[i - 1][j] == f[i][j]) {
            i--;
        } else {
            j--;
        }
    }
}

reverse(ans.begin(), ans.end());
cout << ans;

return 0;

}

И провальный тест:

caacaddeca
abccdbddcd

И ответы, где первый ответ -- от заведомо рабочего кода, а второй -- от моего:

ccddc
cddc
1
  • Да, можно сделать матрицу предков, но это совсем не дело.
    – witaway
    28 ноя 2017 в 6:04

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Посмотрите другие вопросы с метками или задайте свой вопрос.