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

advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

**If you find any mistake above, kindly email to [email protected]**

**Related Posts:**

- Watch Advanced C Programming Videos
- Apply for Computer Science Internship
- Check Computer Science Books
- Check C Books
- Practice BCA MCQs