Как сохранить всю строку LCS, используя рекурсивный подход - PullRequest
Новая
       59

Как сохранить всю строку LCS, используя рекурсивный подход

0 голосов
/ 04 мая 2020

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

#include<bits/stdc++.h>
using namespace std;
set<char>s;
int LCS(string s1, string s2, int i, int j)
{
    if (i == s1.size() || j == s2.size())
    {
        return 0;
    }

    if (s1[i] == s2[j])
    {
        s.insert(s1[i]);
        return 1 + LCS(s1, s2, i + 1, j + 1);
    }
    return max(LCS(s1, s2, i + 1, j), LCS(s1, s2, i, j + 1));

}




int main()
{
#ifndef YOLO
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    string f, d;
    cin >> f >> d;
    cout << LCS(f, d, 0, 0) << endl;
    for (char i : s)
    {
        cout << i;
    }
}

, также возможно ли сохранить LCS, когда я применяю запоминание к этому рекурсивному подходу ??

...