Longest common subsequence is a classic **dynamic programming** problem.

Below Literature is from Wikipedia. Included some introduction to the problem in this article.

The longest common subsequence (LCS) problem is to find the longest subsequence common to all sequences in a set of sequences (often just two) – Wikipedia

For the general case of an arbitrary number of input sequences, the problem is NP-hard .When the number of sequences is constant, the problem is solvable in polynomial time by dynamic programming

It should be noted that the sequence is non-contiguous unlike longest common substring problem where the substring is contiguous.

Additional Reading

Algorithm:

Computing the length of the LCS

function LCSLength(X[1..m], Y[1..n])
C = array(0..m, 0..n)
for i := 0..m
C[i,0] = 0
for j := 0..n
C[0,j] = 0
for i := 1..m
for j := 1..n
if X[i] = Y[j]
C[i,j] := C[i-1,j-1] + 1
else:
C[i,j] := max(C[i,j-1], C[i-1,j])
return C[m,n]

Implementation:

import java.util.Scanner;
public class LCS
{
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);
System.out.println("Enter the first string");
String str1 = input.next();
System.out.println("Enter the Second string");
String str2 = input.next();
int[][] lcs = new int[str1.length()+1][str2.length()+1];
int i;
for(i=0;i<=str1.length();i++)
lcs[i][0] = 0;
for(i=0;i<=str2.length();i++)
lcs[0][i] = 0;
for(i=1;i<=str1.length();i++)
{
for(int j=1;j<=str2.length();j++)
{
if(str1.charAt(i-1) == str2.charAt(j-1))
lcs[i][j]=lcs[i-1][j-1]+1;
else
lcs[i][j]=Math.max(lcs[i-1][j], lcs[i][j-1]);
}
}
System.out.println("The Length of LCS is: "+lcs[str1.length()][str2.length()]);
System.out.println("The LCS is: ");
int x = 0, y = 0;
while(x < str1.length() && y < str2.length())
{
if (str1.charAt(x) == str2.charAt(y))
{
System.out.print(str1.charAt(x));
x++;
y++;
}
else if (lcs[x+1][y] >= lcs[x][y+1]) x++;
else y++;
}
System.out.println();
}
}

OUTPUT:

labuser@ubuntu:~$ java LCS

Enter the first string

AGCAT

Enter the Second string

GAC

The Length of LCS is: 2

The LCS is:

GA

Also this algorithm has formed the basis for UNIX diff command .The diff utility was developed in the early 1970s on the Unix operating system which was emerging from AT&T Bell Labs in Murray Hill, New Jersey. The final version, first shipped with the 5th Edition of Unix in 1974, was entirely written by Douglas McIlroy. This research was published in a 1976 paper co-written with James W. Hunt who developed an initial prototype of diff The algorithm this paper described became known as the **Hunt-McIlroy algorithm**. – Wikipedia

### Like this:

Like Loading...

*Related*