-
Notifications
You must be signed in to change notification settings - Fork 0
/
longest_common_subsequence.cpp
82 lines (66 loc) · 2.06 KB
/
longest_common_subsequence.cpp
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
#include "iostream"
using namespace std;
enum Direction {DEC_A, DEC_B, DEC_BOTH};
struct LCS_box {
int length; // length of LCS up to this point
Direction direction; // represents the direction I need to go to continue the LCS
};
// returns length of LCS, puts contents into buffer
string lcs(string A, string B);
int main() {
string word1 = "0s0o0m0e0t0h0i0n0g";
string word2 = "s1o1m1e1t1h1i1n1g1";
cout << "Enter two words" << endl;
cin >> word1 >> word2;
cout << lcs(word1, word2) << endl;
}
string lcs(string A, string B)
{
// figure out length of LCS of each A[1..a] B[1..b] subarrays
LCS_box matrix[A.length()][B.length()];
for (int a = 0; a < A.length(); a++) {
for (int b = 0; b < B.length(); b++) {
matrix[a][b].length = 0;
if (A[a] == B[b]) {
matrix[a][b].direction = DEC_BOTH;
if (a == 0 || b == 0) {
matrix[a][b].length = 1;
}
else {
matrix[a][b].length = matrix[a - 1][b - 1].length + 1;
}
continue;
}
if (a != 0) {
if (matrix[a-1][b].length >= matrix[a][b].length) {
matrix[a][b].length = matrix[a-1][b].length;
matrix[a][b].direction = DEC_A;
}
}
if (b != 0) {
if (matrix[a][b-1].length >= matrix[a][b].length) {
matrix[a][b].length = matrix[a][b-1].length;
matrix[a][b].direction = DEC_B;
}
}
}
}
// now reconstruct LCS
int a = A.length() - 1;
int b = B.length() - 1;
string answer = "";
while (a >= 0 && b >= 0) {
if (matrix[a][b].direction == DEC_BOTH) {
answer = A[a] + answer;
a--;
b--;
}
else if (matrix[a][b].direction == DEC_A) {
a--;
}
else if (matrix[a][b].direction == DEC_B) {
b--;
}
}
return answer;
}