This is a C Program to find length Longest Commmon Subsequence of a given sequence. LCS Problem Statement: Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences.
Here is source code of the C Program to Find the Longest Increasing Subsequence of a Given Sequence. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
/* A Naive recursive implementation of LCS problem */
#include<stdio.h>
#include<stdlib.h>
int max(int a, int b);
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs(char *X, char *Y, int m, int n) {
if (m == 0 || n == 0)
return 0;
if (X[m - 1] == Y[n - 1])
return 1 + lcs(X, Y, m - 1, n - 1);
else
return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));
}
/* Utility function to get max of 2 integers */
int max(int a, int b) {
return (a > b) ? a : b;
}
/* Driver program to test above function */
int main() {
char X[] = "AGGTAB";
char Y[] = "GXTXAYB";
int m = strlen(X);
int n = strlen(Y);
printf("Length of LCS is %d\n", lcs(X, Y, m, n));
return 0;
}
Output:
$ gcc LCS.c $ ./a.out Length of LCS is 4
Sanfoundry Global Education & Learning Series – 1000 C Programs.
advertisement
Here’s the list of Best Books in C Programming, Data Structures and Algorithms.
Related Posts:
- Practice BCA MCQs
- Check Computer Science Books
- Practice Computer Science MCQs
- Apply for C Internship
- Watch Advanced C Programming Videos