Cod sursa(job #2947321)

Utilizator lucfer444666Leonachi Dianeu lucfer444666 Data 25 noiembrie 2022 21:59:06
Problema Cel mai lung subsir comun Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
#define cin fin
#define cout fout
void lcs(char* X, char* 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;
		char 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<<lcs[k]<<" ";
	}
int main()
	{
		int m,n; cin>>m>>n;
		char A[m];
		char 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);
	}