# Longest Common Subsequence C Program

By | November 24, 2016

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

```#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;
char first_sequence, second_sequence, longest_sequence;

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;
}
for(a = 0; a <= d; a++)
{
temp[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

```#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, second_sequence;
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.

Recommended Programs
C Program To Implement Prim’s Algorithm
C Program To Reverse a String using Stack
C Program To Find Union and Intersection of Two Arrays
C Program To Find IP Address in Linux
C Program To Compare Two Strings
C Program To Concatenate Two Strings
C Program To Generate Random Numbers
Find Smallest Digit in a Number C Program
C Program To Check Skew Symmetric Matrix
C Program To Implement Caesar Cipher Algorithm

## One thought on “Longest Common Subsequence C Program”

1. Parag Vidhate

Just amazing. I really liked the recursive approach for LCS C Program since it prints the longest sequence length.