Make the frequent cases fast and the rare case correct

Computing the length of “Longest common subsequence” of TWO strings and displaying the LCS

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

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
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]


import java.util.Scanner;
public class LCS
	public static void main(String[] args)
		Scanner input = new Scanner(;
		System.out.println("Enter the first string");
		String str1 =;
		System.out.println("Enter the Second string");
		String str2 =;
		int[][] lcs = new int[str1.length()+1][str2.length()+1];
		int i;
			lcs[i][0] = 0;
			lcs[0][i] = 0;
			for(int j=1;j<=str2.length();j++)
				if(str1.charAt(i-1) == str2.charAt(j-1))
					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)) 
            		else if (lcs[x+1][y] >= lcs[x][y+1]) x++;
            		else y++;


labuser@ubuntu:~$ java LCS
Enter the first string
Enter the Second string
The Length of LCS is: 2
The LCS is:

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: