Longest common subsequence in C
The Longest Common Subsequence (LCS) is a concept used in computer science to find the longest sequence of characters that appears in the same order in two given strings. This sequence doesn't necessarily have to be contiguous or appear consecutively in the strings. In simple terms, it's the longest string of characters that both strings have in common.
Let's understand this with an example:
Suppose we have two strings:
String 1: "abcde"
String 2: "ace"
Now, we compare the characters in both strings from left to right to find the LCS between these two strings. We look for characters that are present in both strings in the same order without necessarily being adjacent.
In this example, both strings have the letters 'a' and 'e' in common. However, they are not consecutive. The LCS between the two strings is "ae", which is the longest sequence that appears in the same order in both strings.
The LCS is unaffected by other characters in the strings that don't form part of the common sequence. For example, in the given strings, the letters 'b', 'c', 'd' in String 1 and the letter 'c' in String 2 are not part of the LCS.
Example:
Let's take a program to find the longest common subsequence in C:
#include <stdio.h>
#include <string.h>
int max(int a, int b)
{
return (a > b) ? a : b;
}
int Longest_common_subsequence(char *str1, char *str2, int string_length1, int string_length_2)
{
if (string_length1 == 0 || string_length_2 == 0){
return 0;
}
if (str1[string_length1 - 1] == str2[string_length_2 - 1]){
return 1 + Longest_common_subsequence(str1, str2, string_length1 - 1, string_length_2 - 1);
}
else{
return max(Longest_common_subsequence(str1, str2, string_length1 - 1, string_length_2), Longest_common_subsequence(str1, str2, string_length1, string_length_2 - 1));
}
}
void print_longest_common_subsequence(char *str1, char *str2, int string_length1, int string_length_2, int lcsLength, char *lcs, int index)
{
if (string_length1 == 0 || string_length_2 == 0){
return;
}
if (str1[string_length1 - 1] == str2[string_length_2 - 1])
{
lcs[index - 1] = str1[string_length1 - 1];
print_longest_common_subsequence(str1, str2, string_length1 - 1, string_length_2 - 1, lcsLength - 1, lcs, index - 1);
}else
{
if (Longest_common_subsequence(str1, str2, string_length1 - 1, string_length_2) >Longest_common_subsequence(str1, str2, string_length1, string_length_2 - 1)){
print_longest_common_subsequence(str1, str2, string_length1 - 1, string_length_2, lcsLength, lcs, index);
}
else{
print_longest_common_subsequence(str1, str2, string_length1, string_length_2 - 1, lcsLength, lcs, index);
}
}
}
int main()
{
int string_length_1=0;
int string_length_2=0;
printf("Enter the length of first string and second string \n");
scanf("%d %d",&string_length_1,&string_length_2);
char str1[string_length_1];
char str2[string_length_2];
printf("Enter the first string \n");
scanf("%s",&str1);
printf("Enter the second string \n");
scanf("%s",&str2);
int lcsLength = Longest_common_subsequence(str1, str2, string_length_1, string_length_2);
char lcs[lcsLength + 1];
lcs[lcsLength] = '\0';
print_longest_common_subsequence(str1, str2, string_length_1, string_length_2, lcsLength, lcs, lcsLength);
printf("Longest Common Subsequence: %s\n", lcs);
return 0;
}
Output:
![Longest common subsequence in C](https://static.tutorialandexample.com/c/longest-common-subsequence-in-c1.png)
Explanation:
max(int a, int b):
It is a helper function that returns the maximum of two integers, a and b.
Longest_common_subsequence(char *str1, char *str2, int string_length1, int string_length_2):
The main recursive function calculates the length of the LCS between two strings. It takes four parameters:
str1: It represents the first string.
str2: It represents the second string.
string_length1: It represents the length of the first string.
string_length_2: It represents the length of the second string.
The function recursively compares the characters of the two strings, and if they match, it increments the LCS length by 1 and continues recursively with the remaining substrings. If the characters do not match, the function makes two recursive calls, one by excluding the last character of str1 and the other by excluding the last character of str2. The maximum LCS length from these two recursive calls is returned.
print_longest_common_subsequence(char *str1, char *str2, int string_length1, int string_length_2, int lcsLength, char *lcs, int index):
A recursive function that prints the LCS between two strings. It takes the following parameters:
str1: It represents the first string.
str2: It represents the second string.
string_length1: It represents the length of the first string.
string_length_2: It represents the length of the second string.
lcsLength: It represents the length of the LCS between str1 and str2.
lcs: The array to store the LCS characters.
index: The current index to store the LCS character.
The function follows a similar recursive approach to Longest_common_subsequence(). If the characters at the current indices match, it stores the character in the lcs array and continues recursively with the remaining substrings. Otherwise, it selects the recursive call with the maximum LCS length.
main() function:
The main function reads the input strings and calculates the LCS between them. It performs the following steps:
- Reads the lengths of the first and second strings.
- Declares str1 and str2 as character arrays of appropriate sizes.
- Reads the first and second strings from the user.
- Calculates the length of the LCS using Longest_common_subsequence() function.
- Declares the lcs array with a size of lcsLength + 1 to store the LCS characters.
- Calls print_longest_common_subsequence() to print the LCS.
- Prints the LCS.