uva: 10405 – Longest Common Subsequence (LCS)

10405 – Longest Common Subsequence

Problem analysis:

Given two sequences of characters, print the length of the longest common subsequence of both sequences. For example, the longest common subsequence of the following two sequences:

abcdgh
aedfhr

is adh of length 3.

Solution analysis:

  • LCS – solution of this problem is standard LCS  algorithm

 


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.lang.System;

class Main_10405_LCS {
    /**
     * Author: Mohammad Moniruzzaman
     * UVa ID: 457490     
     */

    public static void main(String[] args) {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Scanner sc = new Scanner(br);
        String str1, str2;
        int[][] lcs;
        int i,j,m,n;
        
        while(sc.hasNext())
        {
            str1 = sc.nextLine();
            str2 = sc.nextLine();
            m = str1.length();
            n = str2.length();
            
            lcs = new int[m+1][n+1];
            
            for(i=1; i <= m; i++)
            {
                for(j=1; j <= n; 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(lcs[m][n]);            
        }
        sc.close();
        sc = null;
    }

}

Advertisements

About M Moniruzzaman
A passionate software engineer, have been developing applications on various platforms such as Android, iPhone, .Net (C#) technologies and web based ASP.NET, PHP, JavaScript, jQuery technologies for more than 10 years. Especially I have expertise on developing applications for Android and iPhone, as well as service oriented, client-server based applications where clients will be reside on Android/iPhone that communicate with WCF(.NET) service hosted on server. I have completed certification in Microsoft Certified Professional Developer (MCPD) on .Net 4 . I have completed my graduation in -- B.Sc. (Engineering) in Computer Science and Engineering, ShahJalal University of Science and Technology, Bangladesh. Thanks, M. Moniruzzaman (Zaman)

Leave a Reply

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

WordPress.com Logo

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

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s

%d bloggers like this: