-
Notifications
You must be signed in to change notification settings - Fork 31
Expand file tree
/
Copy pathLCS.cpp
More file actions
65 lines (57 loc) · 1.7 KB
/
LCS.cpp
File metadata and controls
65 lines (57 loc) · 1.7 KB
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
#include<cstdio>
#include<cstring>
#define MAX 100 // size of each sequence
char str1[MAX], str2[MAX]; // the sequences
/* *********************************************** */
/* This function print the LCS to the screen */
/* Input : A table generated by the LCS_LNT */
/* and the length ot the sequences */
/* Output: None */
/* *********************************************** */
void p_lcs(int b[MAX][MAX], int i, int j)
{
if((i == 0) || (j == 0)) return ;
if(b[i][j] == 1) {
p_lcs(b, i - 1, j - 1);
printf("%3c", str1[i - 1]);
} else if(b[i][j] == 2) p_lcs(b, i - 1, j);
else p_lcs(b, i, j - 1);
}
/* ********************************************* */
/* This function calculate the LCS length */
/* Input : Tow Sequence and an bool I. If */
/* I is FALSE(0) then the function */
/* do not print the LCS and if */
/* TRUE(1) then print using the */
/* above p_lcs function */
/* Output: None */
/* ********************************************* */
void LCS_LNT(bool I)
{
int c[MAX][MAX] = {0}, b[MAX][MAX] = {0}, l1, l2;
l1 = strlen(str1) + 1;
l2 = strlen(str2) + 1;
register int i, j;
for(i = 1; i < l1; i++) {
for(j = 1; j < l2; j++) {
if(str1[i - 1] == str2[j - 1]) {
c[i][j] = c[i - 1][j - 1] + 1;
b[i][j] = 1;
} else if(c[i - 1][j] >= c[i][j - 1]) {
c[i][j] = c[i - 1][j];
b[i][j] = 2;
} else c[i][j] = c[i][j - 1];
}
}
printf("%d\n", c[l1 - 1][l2 - 1]);
if(I) p_lcs(b, l1 - 1, l2 - 1);
}
/* a sample main function */
int main()
{
while(1) {
if(!(gets(str1))) return 0;
if(!(gets(str2))) return 0;
LCS_LNT(1);
}
}