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;
}
Advertisements

Min Priority Queue Implementation Using Array Min Heap

Min Priority Queue Implementation Using Array Min Heap:

The code is explained in comments. This code is implementation of min / minimum priority queue using min heap.

An easy to follow priority queue theory tutorial ( Max Priority Queue, Max Heap ) and with visualizations can be found here.


 Min Priority Queue Implementation C++:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Code:    Min Priority Queue Implementation Using Array Min Heap
 */

#include<iostream>
#include<cstdio>
#include<climits>
#include<cmath>
using namespace std;

#define N 100

struct node{
    char data;
    int key;
} A[N];

/*
 * Initial heap size 0 as heap is empty
 */
int heapsize = 0;

/*
 * Find the parent node
 */
int parent(int i){
    return ceil(i / 2.0 - 1);
}

/*
 * Use for heap insert and decrease key
 * In if condition check if user attempted to increase value instead of decrease
 * Compare child with parent, if child is smaller then swap
 * Now mark that child and apply the same logic until it reaches root node
 */
void decreaseKey(int i, node n){
    if(n.key > A[i].key){
        printf("Error\n");
        return;
    }

    A[i] = n;
    while(i > 0 && A[parent(i)].key > A[i].key){
        std:: swap(A[i], A[parent(i)]);
        i = parent(i);
    }
}

/*
 * Search for a specific node to change its value
 * Returns the index the node being searched
 */
int searchIndex(node n){
    for(int i = 0; i < heapsize; ++i){
        if(A[i].data == n.data)
            return i;
    }
    return heapsize;
}

/*
 * Called initially to create a min heap
 * Also called after a node extraction from min heap
 * Since the smallest value node is at the root of min heap
 * After extraction min heapify is called on root node
 * It compares parent with its children
 * If a smaller child found then its swapped with parent and
 * Min heapify is again called on that child to apply same procedure
 */
void minHeapify(int i){
    int largest;

    int l = 2*i +1;

    if (l < heapsize && A[l].key < A[i].key)
        largest = l;
    else
        largest = i;

    int r = 2*i +2;

    if (r < heapsize && A[r].key < A[largest].key)
        largest = r;

    if (largest != i){
        std::swap(A[i], A[largest]);
        minHeapify(largest);
    }
}

/*
 * Does not extract any items only show the minimum element
 */
node heapMinimum(){
    return A[0];
}

/*
 * Increase heap size to create space for new node
 * Insert the node at that space by calling decrease key function
 */
void heapInsert(node n){
    ++heapsize;
    A[heapsize - 1].key = INT_MAX;
    decreaseKey(heapsize - 1, n);
}

/*
 * Heap size less than zero mean no items in heap so nothing to extract
 * For min heap minimum value is at the root which in here is A[0]
 * Save the root and replace root with last element in the heap and decrease the heap size
 * So the root is still in the array in last position but no longer in the heap
 * Since the last element is now the root the heap may be unbalanced
 * So to balance the heap call min heapify on the root node again
 * Lastly return the saved root
 */
node extractMin(){
    if(heapsize < 0)
        printf("Heap Underflow\n");

    node min = A[0];
    A[0] = A[heapsize - 1];
    --heapsize;
    minHeapify(0);
    return min;
}

/*
 * Every time we extract heap size is automatically reduced
 * So no need change heap size in while loop
 */
void printPriorityQueue(){
    printf("Main Output:\n");
    while(heapsize){
        node ext = extractMin();
        printf("%c %d\n", ext.data, ext.key );
    }
}

/*
 * input data and key for node and insert that node in min priority queue
 */
void inputQueueItems(){
    int i;
    printf("How many nodes?\n");
    scanf("%d", &i); getchar();
    while(i--){
        node n;
        printf("Enter node name and its value:\n");
        scanf("%c%d", &n.data, &n.key);
        getchar();
        heapInsert(n);
    }
}

int main(){

    inputQueueItems();
    printPriorityQueue();


    /*
     * Sample input for quick testing
     * Before using this comment inputQueueItems() function call
     */
    /*
    heapInsert({'z',99});
    heapInsert({'a',9});
    heapInsert({'v',29});
    heapInsert({'x',19});
    heapInsert({'c',95});
    heapInsert({'g',22});
    heapInsert({'b', 1});
    heapInsert({'e', 5});
    heapInsert({'d', 2});
    */
    //decreaseKey( searchIndex({'a', 9}), {'a', 4} );

    return 0;
}