Let us learn how to implement Longest Common Subsequence Problem in C programming. The C program to find the longest subsequence in two strings (sequences) can be implemented using Dynamic Programming and Recursion.
What is Longest Common Sub-Sequence Problem?
In this algorithm, from a given set of strings, we have to find the longest sequence of the characters that is present in the strings.
In other words, the LCS problem is to find the longest subsequence common to all the given subsequences.
Here is the mathematical function for Longest Common Sequence Problem.
Example
First Sequence: MNOPQRS
Second Sequence: MNQSTXYZ
Longest Common Subsequence: MNQS
Length: 4
Method 1: C Program To Implement LCS Problem without Recursion
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 | #include<stdio.h> #include<string.h> void longest_common_subsequence_algorithm(); void print_sequence(int a, int b); int a, b, c, d; int temp[30][30]; char first_sequence[30], second_sequence[30], longest_sequence[30][30]; int main() { printf("\nEnter the First String:\t"); scanf("%s", first_sequence); printf("\nEnter the Second String:\t"); scanf("%s", second_sequence); printf("\nLongest Common Subsequence:\t"); longest_common_subsequence_algorithm(); print_sequence(c, d); printf("\n"); return 0; } void longest_common_subsequence_algorithm() { c = strlen(first_sequence); d = strlen(second_sequence); for(a = 0; a <= c; a++) { temp[a][0] = 0; } for(a = 0; a <= d; a++) { temp[0][a] = 0; } for(a = 1; a <= c; a++) { for(b = 1; b <= d; b++) { if(first_sequence[a - 1] == second_sequence[b - 1]) { temp[a][b] = temp[a - 1][b - 1] + 1; longest_sequence[a][b] = 'c'; } else if(temp[a - 1][b] >= temp[a][b - 1]) { temp[a][b] = temp[a - 1][b]; longest_sequence[a][b] = 'u'; } else { temp[a][b] = temp[a][b - 1]; longest_sequence[a][b] = 'l'; } } } } void print_sequence(int a, int b) { if(a == 0 || b == 0) { return; } if(longest_sequence[a][b] == 'c') { print_sequence(a - 1, b - 1); printf("%c", first_sequence[a - 1]); } else if(longest_sequence[a][b] == 'u') { print_sequence(a - 1, b); } else { print_sequence(a, b - 1); } } |
Method 2: C Program To Print Length Longest Common Subsequence using Recursion
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 | #include<stdio.h> #include<string.h> int longest_sequence(char *first_sequence, char *second_sequence, int l1, int l2); int maximum_value(int p, int q); int main() { int l1, l2, length; char first_sequence[30], second_sequence[30]; printf("\nEnter the First String:\t"); scanf("%s", first_sequence); printf("\nEnter the Second String:\t"); scanf("%s", second_sequence); l1 = strlen(first_sequence); l2 = strlen(second_sequence); length = longest_sequence(first_sequence, second_sequence, l1, l2); printf("\nLength of the Longest Common Subsequence:\t%d\n", length); return 0; } int longest_sequence(char *first_sequence, char *second_sequence, int l1, int l2) { if(l1 == 0 || l2 == 0) { return 0; } if (first_sequence[l1-1] == second_sequence[l2 - 1]) { return 1 + longest_sequence(first_sequence, second_sequence, l1 - 1, l2 - 1); } else { return maximum_value(longest_sequence(first_sequence, second_sequence, l1, l2 - 1), longest_sequence(first_sequence, second_sequence, l1 - 1, l2)); } } int maximum_value(int p, int q) { return (p > q) ? p : q; } |
Output
In case you get any compilation errors or any doubts in this C program to print Longest Common Subsequence problem algorithm, let us know about it in the comment section below.
Just amazing. I really liked the recursive approach for LCS C Program since it prints the longest sequence length.