Algorithms/longest_common_sub.cpp at master · SharadSrc/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

/*
 * Name :sharad Dixit
 * Institute :IIIT -A
 */

#include <iostream>
#include <vector>

using namespace std;

void print(string b[][100],string s,int i,int j)
{
	if ( i == 0 || j == 0) {
		return ;
	}
	if (b[i][j] == "NW") {
		print(b,s,i-1,j-1);

	cout << s[i-1] << "  ";
	}

	else if (b[i][j] == "N") {
		print(b,s,i-1,j);
	}
	else {
		print(b,s,i,j-1);
	}


}

void lcs( string s1, string s2 )
{
	int l1;
	int l2;
	int c[100][100];
	string b[100][100];

	l1 = s1.size();
	l2 = s2.size();

//	for ( int i = 0; i<= l1; i++ ) {
//		c[i][0] = 0;
//	}

//	for ( int j = 0; j<= l2; j++ ) {
//		c[0][j] = 0;
//	}

	for ( int i = 1; i<=l1; i++){
		for ( int j = 1; j<=l2; j++){
			if (s1[i-1] == s2[j-1]){
				c[i][j]= c[i-1][j-1] +1;
				b[i][j]="NW";

			}
			else {
				if (c[i -1][j] >= c[i][j-1] ){
					c[i][j] = c[i-1][j];
					b[i][j] = "N";
				}
				else{
					c[i][j] = c[i][j-1];
					b[i][j] = "W";
				}
			}
		}
	}

	for ( int i = 0;i <= l1; i++){
		for ( int j =0 ;j<= l2; j++){
			cout << c[i][j] <<"  ";
		}
		cout << endl;
	}
	cout << "LONGEST COMMON SUBSEQUENCE"<< endl;
	print(b,s1,l1,l2);

	cout << endl;
}


int main()
{
	string s1;
	string s2;

	cin >> s1;
	cin >> s2;

	lcs(s1,s2);
}