public class Soru32 {     // Returns length of LCS for X[0..m-1], Y[0..n-1]     static void lcs(String X, String Y, int m, int n)     {         int[][] L = new int[m+1][n+1];         // Following steps build L[m+1][n+1] in bottom up fashion. Note         // that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1]         for (int i=0; i<=m; i++)         {             for (int j=0; j<=n; j++)             {                 if (i == 0 || j == 0)                     L[i][j] = 0;                 else if (X.charAt(i-1) == Y.charAt(j-1))                     L[i][j] = L[i-1][j-1] + 1;                 else                     L[i][j] = Math.max(L[i-1][j], L[i][j-1]);             }         }         // Following code is used to print LCS         int index = L[m][n];         int temp = index;         // Create a character array to store the lcs string         char[] lcs = new char[index+1];         lcs[index] = '\u0000'; // Set the terminating character         // Start from the right-most-bottom-most corner and         // one by one store characters in lcs[]         int i = m;         int j = n;         while (i > 0 && j > 0)         {             // If current character in X[] and Y are same, then             // current character is part of LCS             if (X.charAt(i-1) == Y.charAt(j-1))             {                 // Put current character in result                 lcs[index-1] = X.charAt(i-1);                                 // reduce values of i, j and index                 i--;                 j--;                 index--;                 }             // If not same, then find the larger of two and             // go in the direction of larger value             else if (L[i-1][j] > L[i][j-1])                 i--;             else                 j--;         }         // Print the lcs         System.out.print("LCS of "+X+" and "+Y+" is ");         for(int k=0;k<=temp;k++)             System.out.print(lcs[k]);     }         // driver program     public static void main (String[] args)     {         String S1 = "BCDAACD";         String S2 = "ACDBAC";         int m = S1.length();         int n = S2.length();         lcs(S1, S2, m, n);     } }   Explain the above algorithm

Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
icon
Related questions
Question

public class Soru32
{
    // Returns length of LCS for X[0..m-1], Y[0..n-1]
    static void lcs(String X, String Y, int m, int n)
    {
        int[][] L = new int[m+1][n+1];

        // Following steps build L[m+1][n+1] in bottom up fashion. Note
        // that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1]
        for (int i=0; i<=m; i++)
        {
            for (int j=0; j<=n; j++)
            {
                if (i == 0 || j == 0)
                    L[i][j] = 0;
                else if (X.charAt(i-1) == Y.charAt(j-1))
                    L[i][j] = L[i-1][j-1] + 1;
                else
                    L[i][j] = Math.max(L[i-1][j], L[i][j-1]);
            }
        }

        // Following code is used to print LCS
        int index = L[m][n];
        int temp = index;

        // Create a character array to store the lcs string
        char[] lcs = new char[index+1];
        lcs[index] = '\u0000'; // Set the terminating character

        // Start from the right-most-bottom-most corner and
        // one by one store characters in lcs[]
        int i = m;
        int j = n;
        while (i > 0 && j > 0)
        {
            // If current character in X[] and Y are same, then
            // current character is part of LCS
            if (X.charAt(i-1) == Y.charAt(j-1))
            {
                // Put current character in result
                lcs[index-1] = X.charAt(i-1);
               
                // reduce values of i, j and index
                i--;
                j--;
                index--;    
            }

            // If not same, then find the larger of two and
            // go in the direction of larger value
            else if (L[i-1][j] > L[i][j-1])
                i--;
            else
                j--;
        }

        // Print the lcs
        System.out.print("LCS of "+X+" and "+Y+" is ");
        for(int k=0;k<=temp;k++)
            System.out.print(lcs[k]);
    }
   
    // driver program
    public static void main (String[] args)
    {
        String S1 = "BCDAACD";
        String S2 = "ACDBAC";
        int m = S1.length();
        int n = S2.length();
        lcs(S1, S2, m, n);
    }
}

 

Explain the above algorithm?

Expert Solution
steps

Step by step

Solved in 2 steps

Blurred answer
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY