-
Notifications
You must be signed in to change notification settings - Fork 364
/
Longest_Common_Subsequence.c
75 lines (64 loc) · 2.2 KB
/
Longest_Common_Subsequence.c
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
#include <stdio.h>
#include <string.h>
#define MAX 100
void lcsAlgo(char S1[],char S2[])
{
int i, j, m, n;
int LCS_table[20][20];
m = strlen(S1); //length of string 1
n = strlen(S2); //Length of string 2
//This base case
for (i = 0; i <= m; i++)
LCS_table[i][0] = 0;
for (i = 0; i <= n; i++)
LCS_table[0][i] = 0;
//MAIN LCS LOGIC
/*Here firstly we are checking that at current state if the indexes of the both string are equal than we will add 1 to it and decrease our both index pointers
after that if our current indexes did not match we will not add anything but instead of that we are checking for the alternate indexes value*/
for (i = 1; i <= m; i++)
{
for (j = 1; j <= n; j++)
{
if (S1[i - 1] == S2[j - 1])
LCS_table[i][j] = LCS_table[i - 1][j - 1] + 1; //this is the case when both are equal
else if (LCS_table[i - 1][j] >= LCS_table[i][j - 1])
LCS_table[i][j] = LCS_table[i - 1][j]; //this is for alternate index check
else
LCS_table[i][j] = LCS_table[i][j - 1]; //this is for alternate index check
}
}
int index = LCS_table[m][n];
printf("Length of longest common subsequence is %d\n",index-1);
char lcsAlgo[MAX + 1];
lcsAlgo[index] = '\0';
/*As we know length of longest common subsequence is stored in LCS_table[m][n] so we fetch that length from LCS_table[m][n] and start iterating from the last indexes
and here we will check 3 things if both indexes values are equal then we will add that to our lcsAlgo and if they are not equal that means the value must be come from
maximum of previous column or row so whaterver is the maximum value according to that we change our i,j pointers*/
i = m, j = n;
while (i > 0 && j > 0)
{
if (S1[i - 1] == S2[j - 1])
{
lcsAlgo[index - 1] = S1[i - 1];
i--;
j--;
index--;
}
else if (LCS_table[i - 1][j] > LCS_table[i][j - 1])
i--;
else
j--;
}
printf("S1 : %s \nS2 : %s \n", S1, S2);
printf("LCS: %s", lcsAlgo);
}
int main()
{
char s1[MAX],s2[MAX];
printf("Enter string 1 ");
fgets(s1,MAX, stdin);
printf("Enter string 2 ");
fgets(s2,MAX,stdin);
lcsAlgo(s1,s2);
printf("\n");
}