Cod sursa(job #3142731)

Utilizator thinkphpAdrian Statescu thinkphp Data 23 iulie 2023 20:37:56
Problema Cel mai lung subsir comun Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>

#define FIN "cmlsc.in"
#define FOUT "cmlsc.out"

using namespace std;

ifstream fin(FIN);
ofstream fout(FOUT);


int lcs(int *str1, int *str2, int n, int m) {
    
    int table[n+1][m+1];

    for(int i = 0; i <= n; ++i) {

        for(int j = 0; j <= m; ++j) {

            if(i == 0 || j == 0) table[i][j] = 0;

            else if(str1[i-1] == str2[j-1]) {

                 table[i][j] = 1 + table[i-1][j-1];

            } else {
                
                 table[i][j] = max(table[i][j-1], table[i-1][j]);
            }
        }
    }

    cout<<table[n][m]<<endl;

    int i = n, j = m, index = table[n][m];    

    int lcs[index+1];    

    while(i > 0 && j > 0) {

          if(str1[i-1] == str2[j-1]) {

              lcs[index-1] = str1[i-1];

              i--;j--;index--;

          } else if(table[i-1][j] > table[i][j-1]) {

              i--;
          } else {
              j--;
          }
    }
    for(int i = 0; i < table[n][m]; ++i) cout<<lcs[i]<<" ";    

}

int main() {
    int n,m;
    fin>>n>>m;    
    int arr1[1000], arr2[1000];
    for(int i = 0; i < n; ++i) fin>>arr1[i];
    for(int i = 0; i < m; ++i) fin>>arr2[i];
    lcs(arr1,arr2,n,m);
}