package ex3.p1;

public class Cmsc {
	private char[] x;
	private char[] y;
	
	private String[][] mat;
 	
	public Cmsc(char[] x, char[] y) {
		this.x = x;
		this.y = y;
		this.mat = new String[x.length + 1][y.length + 1];
	}

	public void compute(){
		int i, j;
		for (i = 1; i <= x.length; i++){
			for (j = 1; j <= y.length; j++){
				if (x[i-1] == y[j-1]) {
					mat[i][j] = mat[i-1][j-1] + "" + x[i];
//					mat[i][j] = 1 + mat[i-1][j-1];
				}
				else {
					if (mat[i-1][j].length() >= mat[i][j-1].length())
					{
						mat[i][j] = mat[i][j] + mat[i-1][j];
					}
					else
						mat[i][j] = mat[i][j] + mat[i][j-1];
				}
			}
		}
	}
	
	public void print (){
		for (int i = 0; i <= x.length+1; i++){
			for (int j = 0; j <= y.length+1; j++)
			if (mat[i][j] != null)
			{
				System.out.print(mat[i][j] + " ");
			}
			System.out.println();
		}
	}
//	
//	public void traceback (int i, int j, int crt){
//		
//		
//		if (mat[i][j] < crt)
//		{
////			System.out.print(mat[i][j] +" ");
//			crt = mat[i][j];
//			System.out.print(x[i-1]);
//		}
//		
//		mat[i][j] = 0;
//		
//		if (mat[i+1][j] != 0)
//			traceback(i+1,j, crt);
//		if (mat[i][j+1] != 0)
//			traceback(i, j+1, crt);
//		if (mat[i-1][j] != 0)
//			traceback(i-1, j, crt);
//		if (mat[i][j-1] != 0)
//			traceback(i, j-1, crt);
//	}
//	
	public static void main(String[] args) {
		char [] x = {'P','R','O','G','R','A','M'};
		char [] y = { 'R','A','N','D','O','M'};
		Cmsc c = new Cmsc(x, y);
		c.compute();
		c.print();
		
//		c.traceback(c.mx-1 , c.my-1, Integer.MAX_VALUE);
	}

}