Cod sursa(job #1553395)

Utilizator D4n13LMuntean Dan Iulian D4n13L Data 19 decembrie 2015 19:26:09
Problema Cel mai lung subsir comun Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.34 kb
package cmlsc;
import java.io.*;
import java.util.*;
public class Main {

	public static void refac(int mat[][],int a[],int b[], int p, int q,PrintWriter out){
		
		if(p == 0 || q == 0)
			return;
		if(a[p] == b[q])
		{
			refac(mat,a,b,p-1,q-1,out);
			out.print(a[p]+ " ");
			return;
			
		}
		if(mat[p-1][q] > mat[p][q-1])
			refac(mat,a,b,p-1,q,out);
		else
			refac(mat,a,b,p,q-1,out);
		
	}
	
	public static void main(String[] args) {
	try{
		Scanner in = new Scanner(new File("cmlsc.in"));
		int m = in.nextInt();
		int n = in.nextInt();
		int[] a = new int[m+1];
		int[] b = new int[n+1];
		for(int i = 1; i <= m; i++)
			a[i]= in.nextInt();
		for(int i = 1; i <= n ;i++)
			b[i]= in.nextInt();
		int[][] mat = new int[m+1][n+1];
		for(int i = 1; i <= m ; i++)
			for(int j = 1; j <= n; j++)
			{
				if(a[i] == b[j])
					mat[i][j] = 1 + mat[i-1][j-1];
				else
					mat[i][j] = (mat[i-1][j] > mat[i][j-1])?mat[i-1][j]:mat[i][j-1];
						
				
			}
			int p= 0,q = 0;
			for(int i = 1; i <= m; i++)
			{
				
				for(int j = 1; j <= n; j++)
				{
				//	System.out.print(mat[i][j] + " ");
					if(mat[i][j]>mat[p][q])
					{
						p = i;
						q = j;
					}
				}
			}
			PrintWriter out = new PrintWriter("cmlsc.out");
			out.println(mat[p][q]);
			refac(mat,a,b,p,q,out);
			in.close();
			out.close();
			
		
		}
		catch(FileNotFoundException e){

		}

	}
}