#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define max 99
int way[max][max];
int n,m;
int PrintLCD(char *subseq1, char *subseq2, int i, int j){
//printf("%d %d \n",i,j);
//printf("%d \n",way[i][j]);
//if(i==0 || j==0)return 0;
if(way[i][j] == 1){
PrintLCD(subseq1,subseq2,i-1,j-1);
printf("%c",subseq1[i]);
}
if(way[i][j] == 2){
PrintLCD(subseq1,subseq2,i-1,j);
}
if(way[i][j] == 3){
PrintLCD(subseq1,subseq2,i,j-1);
}
if(way[i][j] == 4){
	//printf("\n %d",way[i][j]);
	way[i][j]=2;
		PrintLCD(subseq1,subseq2,n-1,m-1);
			printf("\n");
	PrintLCD(subseq1,subseq2,i,j-1);


}

return 0;


}

int main(){

/*
	a	b	d	c
	0	0	0	0
a0	1	1	1	1
b0	1	2	2	2
c0	1	2	2	3
d0	1	2	3	3




1	3	3	3
2	1	3	3
2	2	4	1
2	2	1	4

*/
//1-skos 2-gora 3-lewo 4-gora/lewo
//1-\ 2-up 3-left 4-both

int i,j;

char A[15],B[15];
char subseq1[16]={'~'};
char subseq2[16]={'~'};

printf("Podaj pierwszy ciag: ");
scanf("%s",A);
printf("\nPodaj drugi ciag: ");
scanf("%s",B);
printf("\n");
strcat(subseq1,A);
strcat(subseq2,B);

m=strlen(subseq1);
n=strlen(subseq2);
int C[n][m];
for(i=0;i<m;i++) C[i][0]=0;
for(j=1;j<n;j++) C[0][j]=0;
for(i=1;i<m;i++){
                for(j=1;j<n;j++){
                                  if(subseq1[i] == subseq2[j]){
                                                  C[i][j] = C[i-1][j-1]+1;
                                                  way[i][j] = 1;

                                                  }
                                  else if(C[i-1][j]>=C[i][j-1]){
                                                              C[i][j] = C[i-1][j];
                                                              if(C[i-1][j]==C[i][j-1])	{
															  way[i][j] = 4;
														}else{
															  way[i][j] = 2;
                                                        			}
															}
                                        else{
                                          C[i][j] = C[i][j-1];
                                          way[i][j] = 3;
                                            }
                                  }
                    }
/*************
rekurencja(i.j)

jezeli w way ij:

4 rekurencja i-1j
rekurencja ij-1
3 rekurencja i-1j
2 rekurencja ij-1
1 printf("%c",subseq1[i]);
***********


*/
printf("Najdluzszy podciag to: ");
PrintLCD(subseq1,subseq2,n-1,m-1);
printf("\n");

	return 0;
}