Longest common subsequence(LCS)

1. /* 
2.  used 1 for diagonal, 
3.  2 for up and 
4.  3 for backward or left 
5. */  
6.   
7.   
8. #include<bits/stdc++.h>  
9. using namespace std;  
10. #define M 20  
11.   
12. int a[M][M],b[M][M];  
13. string s1,s2;  
14.   
15. void print(int i,int j){  
16.     if(i==0 || j==0)  
17.         return;  
18.   
19.     if(b[i][j]==1){  
20.         print(i-1,j-1);  
21.         cout<<s1[i-1];  
22.     }  
23.     else if(b[i][j]==2)  
24.         print(i-1,j);  
25.     else  
26.         print(i,j-1);  
27. }  
28.   
29. void lcs(){  
30.     int n=s1.size();  
31.     int m=s2.size();  
32.   
33.     for(int i=1;i<=n;i++){  
34.         for(int j=1;j<=m;j++){  
35.             if(s1[i-1]==s2[j-1]){  
36.                 a[i][j]=a[i-1][j-1]+1;  
37.                 b[i][j]=1;  
38.             }  
39.             else if(a[i-1][j]>a[i][j-1]){  
40.                 a[i][j]=a[i-1][j];  
41.                 b[i][j]=2;  
42.             }  
43.             else{  
44.                 a[i][j]=a[i][j-1];  
45.                 b[i][j]=3;  
46.             }  
47.         }  
48.     }  
49. }  
50.   
51. int main()  
52. {  
53.     cin>>s1;  
54.     cin>>s2;  
55.     lcs();  
56.     print(s1.size(),s2.size());  
57.     return 0;  
58. }  

Read More