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.**

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

advertisement

advertisement

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

**Next Steps:**

- Get Free Certificate of Merit in C Programming
- Participate in C Programming Certification Contest
- Become a Top Ranker in C Programming
- Take C Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

**Related Posts:**

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