The Longest Common Subsequence Discussions | Algorithms | HackerRank
  • + 0 comments
    //package solve_problems;
    /*
     * 2024 ^_^
     *ThinhNguyen97
     * 
     */
    
    import java.math.BigInteger;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.HashMap;
    import java.util.Set;
    import java.util.HashSet;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Map;
    import java.util.Queue;
    import java.util.Scanner;
    import java.util.Stack;
    
    
    
    public class Solve_problems 
    {       
        static void solve(int[] X, int[] Y) {
            int n = X.length, m = Y.length;
            int[][] dp = new int[n + 1][m + 1];
            for (int i = 0; i <= n; i++)
                dp[i][0] = 0;
    
            for (int i = 0; i <= m; i++)
                dp[0][i] = 0;
    
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= m; j++) 
                {
                    if (X[i - 1] == Y[j - 1])
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    else
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
    
            // Reconstruct the LCS
            int lcsLength = dp[n][m];
            int[] lcs = new int[lcsLength]; // Array to hold the LCS
            int index = lcsLength - 1;
            int i = n, j = m;
            while (i > 0 && j > 0) {
                if (X[i - 1] == Y[j - 1]) {
                    // Current elements match, so they are part of the LCS
                    lcs[index] = X[i - 1];
                    i--;
                    j--;
                    index--;
                } else {
                    // Move to the cell that gives maximum length of LCS
                    if (dp[i - 1][j] > dp[i][j - 1])
                        i--;
                    else
                        j--;
                }
            }
    
            // Print the LCS
            //System.out.println("Length of Longest Common Subsequence: " + lcsLength);
            //System.out.print("Longest Common Subsequence: ");
            for (int k = 0; k < lcsLength; k++)
                System.out.print(lcs[k] + " ");
            
            //System.out.println();
        }
    
    
        public static void main(String[] args) 
        {
            Scanner sc = new Scanner(System.in);
            ////////
            int n=sc.nextInt(), m=sc.nextInt();
            int[] X=new int[n];
            for(int i=0;i<n;i++)
                X[i]=sc.nextInt();
            
            int[] Y=new int[m];
            for(int i=0;i<m;i++)
                Y[i]=sc.nextInt();
            solve(X, Y);
                
            
            
            // Close the Scanner instance
            sc.close();
        }
    }