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:


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;
            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;
                        lcs[i][j] = Math.max( lcs[i-1][j], lcs[i][j-1] );
        sc = null;



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 )

Connecting to %s

%d bloggers like this: