• Source 
    1. /*
    2. ****************************************
    3. Problem: Longest Common Subsequence
    4. ****************************************
    5. Ashis Kumar Chanda
    6. ID:   1624
    7. CSE,  DU
    8. ****************************************
    9. ****************************************
    10. */
    11. //  dynamic problem = DP
    12.  
    13. /* 	This code done for char LCS */
    14.  
    15. #include<stdio.h>
    16. #include<string.h>
    17.  
    18. #define M 50
    19.  
    20. int c[M][M], b[M][M]={0};
    21. char x[M], y[M];
    22.  
    23.  
    24. void print( int i, int j)
    25. {
    26. 	if( i==0 || j==0)
    27. 		return ;
    28. 	if( b[i][j]==3 )// get same char
    29. 	{
    30. 		print(i-1, j-1);
    31. 		printf("%c",x[i]);
    32. 	}
    33. 	else if( b[i][j]==2)
    34. 		print(i-1, j);
    35. 	else
    36. 		print(i, j-1);
    37. }
    38.  
    39.  
    40. int main()
    41. {
    42. 	int i,j, m,n;
    43. 	char ch;
    44.     //********* First String input ******
    45. 	i=1;
    46. 	x[0]='0';
    47. 	while( scanf("%c",&ch)!=EOF){
    48. 		if( ch==10 )break;
    49. 		x[i]=ch;
    50. 		i++;
    51. 	}
    52. 	x[i]=NULL;
    53.  
    54. 	//********* Second String input ******
    55. 	i=1;
    56. 	y[0]='1';
    57. 	while( scanf("%c",&ch)!=EOF){
    58. 		if( ch==10 )break;
    59. 		y[i]=ch;
    60. 		i++;
    61. 	}
    62. 	y[i]=NULL;
    63.  
    64. 	m= strlen(x);
    65. 	n= strlen(y);
    66.  
    67.  
    68. 	//************** LCS
    69. 	for(i=0;i<M ;i++)
    70. 		c[i][0]=0;
    71.  
    72. 	for(i=0;i<M ;i++)
    73. 		c[0][i]=0;
    74.  
    75. 	for( i=1; i< m; i++){//  must start from 1
    76. 		for( j=1; j< n; j++)
    77. 		{
    78. 			if( x[i]==y[j]){
    79. 				c[i][j]= c[i-1][j-1] +1;
    80. 				b[i][j]= 3;	// same , sign \\
    81.  
    82. 			}
    83. 			else if (c[i-1][j] >= c[i][j-1] )
    84. 			{
    85. 				c[i][j]=c[i-1][j];
    86.  			    b[i][j] = 2;// sign |
    87. 			}
    88. 			else{
    89. 				c[i][j]=c[i][j-1];
    90.  			    b[i][j] = 1;  // sign <-
    91. 			}
    92. 		}
    93. 	}
    94.  
    95. 	printf("\n output : ");
    96. 	// *********  Now print
    97. 	print(m-1, n-1);//  call by last cell index,  m is strlen
    98.  
    99. 	printf("\n Lenght is : %d\n", c[m-1][n-1] );
    100. 	printf("\n\n	Thanks . . .\n\n");
    101. 	getchar();
    102.  
    103. 	return 0;
    104. }
    105.  
    106.