Cod sursa(job #2947792)

Utilizator lucfer444666Leonachi Dianeu lucfer444666 Data 26 noiembrie 2022 18:22:56
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
#define cin fin
#define cout fout
void lcs(int* X, int* Y, int m, int n)
	{
		int L[m+1][n+1];
		for(int i=0;i<=m;i++)	
			{
				for(int j=0;j<=n;j++)
					{
						if(i==0||j==0)
							L[i][j]=0;
						else if(X[i-1]==Y[j-1])
							L[i][j]=L[i-1][j-1] +1;
						else L[i][j]=max(L[i-1][j],L[i][j-1]);
					}
			}
		int index=L[m][n];
		int lg=index;
		int lcs[index+1];
		/* lcs[index] = '\0';*/
		int i=m; int j=n;
		while(i>0&&j>0)
			{
				if(X[i-1]==Y[j-1])
					{
						lcs[index-1]=X[i-1];
						i--; j--; index--;
					}
				else if(L[i-1][j]>L[i][j-1])
					i--;
				else 
					j--;
			}
		cout<<lg<<"\n";
		for(int k=0;k<lg;k++) cout<<int(lcs[k])<<" ";
	}
int main()
	{
		int m,n; cin>>m>>n;
		int A[m];
		int B[n];
		for(int i=0;i<m;i++) cin>>A[i];
		for(int i=0;i<n;i++) cin>>B[i];	
		lcs(A,B,m,n);
	}