вывести самую длинную общую подпоследовательность - PullRequest
Новая
       6

вывести самую длинную общую подпоследовательность

0 голосов
/ 04 марта 2019

Код печатает самую длинную общую подпоследовательность.Я сделал это с памяткой.Но ответ неверный.Помогите, пожалуйста.

Первая строка - это длина массива
Следующие 2 строки - это последовательность

Например:

Ввод 

5 6

1 2 3 4 1

3 4 1 2 1 3

Вывод 

1 2 3

Или любой другой LCS длиной 3

Но мое решение дает ответ как 

3 4 1 2 1

Мой код: 

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

vector<int> lcs(int a[],int b[],int n,int m, unordered_map<string ,vector<int> > &map1){

    vector<int>v;
    vector<int>v1;
    vector<int>v2;
    if(n<0||m<0)
    {
        return v;
    }



    stringstream na;
    na<<n;
    string n1=na.str();
    stringstream ma;
    ma<<m;
    string m1=ma.str();
    string num =n1 + "#" + m1;


    if(map1.find(num)!=map1.end())
    return map1[num];
    if(a[n]==a[m]){
        v1=lcs(a,b,n-1,m-1,map1);
        v1.push_back(a[n]);
        map1[num]=v1;
        return v1;
    }
    v1=lcs(a,b,n-1,m,map1);
    v2=lcs(a,b,n,m-1,map1);

    v1.size()>v2.size() ? map1[num]=v1 : map1[num]=v2;
    return map1[num];
}






int main(){
    int t;
    int n,m;
    cin>>n>>m;
    int *a=new int[n];
    int *b=new int[m];
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<m;i++)
        cin>>a[i];
    vector<int>v;
    unordered_map<string,vector<int> > map1;
    v=lcs(a,b,n-1,m-1,map1);
    for(int i=0;i<v.size();i++)
        cout<<v[i]<<" ";
    cout<<"\n";
}
...