LCS Algorithm Practice Sheet With Solution Steps

LCS Algorithm blank sheet made with a sample input from uva 10405 longest common subsequence. See this and this tutorial to have a better understanding.


LCS Table with Little Hint:

lcs_algorithm_blank_sheet
lcs_algorithm_blank_sheet

LCS Table with Hints:

lcs_blank_sheet_with_hints
lcs_blank_sheet_with_hints

Completed LCS Table:

lcs_completed_table
lcs_completed_table

LCS Algorithm Table Fill and Print Code with short tutorial

NOTE:

LCS is a very important algorithm and has many uses in computer science. What is a longest common sub sequence? learn about it in Wikipedia.

This tutorial (although not a good one) is an attempt to try to clear concept for LCS Algorithm which is used in UVA problem 10405 (Solution). Here I have used example 3 from that problem.

The table filling method and a practice sheet for this problem can be found in here with better info-graphics.


Instructions:

For the LCS table we define a 2D matrix with a safe size. We can use one string row-wise ( tracked with i ) and another string column-wise ( tracked with j ). It doesn’t matter which way we layout the strings.


The way to fill the table or the 2D matrix is,

  1. If the characters match then take value from row above and left column then add 1 to it and set it as the value of current position.
  2. If characters do not match then take the biggest value from either the row above in the same column or from the left column in the same row, whichever may be the biggest.

We can also print the LCS string the same way in following this concept,

  1. We start at the bottom right corner position of the matrix then trace backwards.
  2. If the characters at the position of current row and column match then print that character and move to left column and row above in the matrix.
  3. If the characters at the position of current row and column do not match then either go to row above or left column depending on whichever is holding the biggest value.

 

Mechanism:

LCS table filling tutorial
LCS table filling tutorial
Print the longest common sequence from generated table tutorial
Print the longest common sequence from generated table tutorial

 

Code/Algorithm LCS String Print:

Please DO NOT try to submit this. This is not the required solution for problem 10405. If you want solution or the inputs to that problem visit this link. Input for this program is two strings. Inputs from problem 10405 will work fine.   

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: LCS Print
 * MUST READ: THIS IS NOT A SOLUTION TO UVA 10405
 */

#include<stdio.h>
#include<string.h>
#define SIZE 1024

static char x[SIZE], y[SIZE];
static int lcs[SIZE][SIZE];

int maxval(int a, int b){
    return a > b ? a : b;
}

/**
 * Print the LCS string
 */
void PrintLCS(int i, int j){
    if(i == 0 || j == 0)
        return;

    if(x[i-1] == y[j-1]){
        PrintLCS(i-1, j-1);
        printf("%c", x[i-1]);
    }
    else if(lcs[i][j-1] > lcs[i-1][j]){
        PrintLCS(i, j-1);
    }
    else
        PrintLCS(i-1, j);
}

int main(){
    register int i, j;

	while(gets(x) && gets(y)){

        int xlen = strlen(x);
        int ylen = strlen(y);

        /*
         * Set the first row and column to zero
         */
        for(i = 0; i <= xlen; ++i)
            lcs[i][0] = 0;

        for(i = 1; i <= ylen; ++i)
            lcs[0][i] = 0;

        /*
         * If both of the characters in string are same then we can reduce both string size by 1 length and calculate rest
         * Else among sub problems by reducing one string and keeping the other one same find the one with the max length
         */
        for(i = 1; i <= xlen; ++i){
            for(j = 1; j <= ylen; ++j){
                if(x[i-1] == y[j-1])
                    lcs[i][j] = lcs[i-1][j-1] + 1;
                else
                    lcs[i][j] = maxval(lcs[i-1][j], lcs[i][j-1]);
            }
        }

        /**
         * Print the LCS string
         */
        printf("LCS String: ");
        PrintLCS(xlen, ylen);
        printf("\n");

        /*
         * The max length is at the bottom right corner of the table
         */
        printf("LCS Length: %d\n", lcs[xlen][ylen] );

	}
	return 0;
}

UVA Problem 10405 – Longest Common Subsequence Solution

UVA Problem 10405 – Longest Common Subsequence Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

This one is a fun problem. For this problem we need to find Longest Common Sub Sequence length of two given strings. We can solve this using LCS Algorithm discussed in Introduction to Algorithms book. This algorithm is explained in Wikipedia and other programming language implementations can be found here.

I have provided two dynamic programming implementations below with one top down memoized ( *Slower ) and a bottom up ( *Faster ) solution.

Take the string inputs carefully there may be empty lines in between.

Overview:

Simple explanation for solution technique is we apply Dynamic Programming techniques. There are overlapping sub problems that we can combine to get original solutions.

Starting from the end of both strings. If both of the characters in string are same then we can reduce both string size by 1 length. So now if do the reverse meaning add 1 we get original solution.

In case both characters are not same keeping one string same we reduce the other one by 1 length and try to match the last characters again.

This way if two characters are  same we increase LCS length count. Among the sub problem we choose the one with longest length.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

bcacbcabbaccbab
bccabccbbabacbc

a1b2c3d4e
zz1yy2xx3ww4vv

abcdgh
aedfhr

abcdefghijklmnopqrstuvwxyz
a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p0q0r0s0t0u0v0w0x0y0z0

abcdefghijklmnzyxwvutsrqpo
opqrstuvwxyzabcdefghijklmn

 


Output:

11
4
3
26
14

Bottom Up Memoized Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10405 Longest Common Subsequence ( LCS )
 * Method:  Memorized Recursive / Top Down Solution
 */

#include<stdio.h>;
#include<string.h>;
#define SIZE 1024

static char x[SIZE], y[SIZE];
static int lcs[SIZE][SIZE];

int maxval(int a, int b){
    return a > b ? a : b;
}

/*
 * If the value is not -1 then it means the value of that sub problem is
 * already calculated. Just return that calculated value
 * If both of the characters in string are same then we can reduce both string size by 1 length and calculate rest
 * Else among sub problems by reducing one string and keeping the other one same find the one with the max length
 */
int LCS(int i, int j){
    if(lcs[i][j] != -1)
        return lcs[i][j];

    if(x[i-1] == y[j-1])
        lcs[i][j] = LCS(i-1, j-1) + 1;
    else
        lcs[i][j] = maxval( LCS(i-1, j), LCS(i, j-1) );

    return lcs[i][j];
}

int main(){
    register unsigned i, j;
	while(gets(x) && gets(y)){

        int xlen = strlen(x);
        int ylen = strlen(y);

        /*
         * Set -1 to all positions to indicate there are no calculated value
         */
        for(i = 1; i <= xlen; ++i)
            for(j = 1; j <= ylen; ++j)
                lcs[i][j] = -1;

        printf("%d\n", LCS(xlen,ylen) );

	}
	return 0;
}

Top Down DP Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10405 Longest Common Subsequence ( LCS )
 * Method:  Top Down Dynamic Programming Solution
 */

#include<stdio.h>
#include<string.h>
#define SIZE 1024

static char x[SIZE], y[SIZE];
static int lcs[SIZE][SIZE];

int maxval(int a, int b){
    return a > b ? a : b;
}

int main(){
    register int i, j;

	while(gets(x) && gets(y)){

        int xlen = strlen(x);
        int ylen = strlen(y);

        /*
         * If both of the characters in string are same then we can reduce both string size by 1 length and calculate rest
         * Else among sub problems by reducing one string and keeping the other one same find the one with the max length
         */
        for(i = 1; i <= xlen; ++i){
            for(j = 1; j <= ylen; ++j){
                if(x[i-1] == y[j-1])
                    lcs[i][j] = lcs[i-1][j-1] + 1;
                else
                    lcs[i][j] = maxval(lcs[i-1][j], lcs[i][j-1]);
            }
        }

        /*
         * The max length is at the bottom right corner of the table
         */
        printf("%d\n", lcs[xlen][ylen] );

	}
	return 0;
}