The Longest Common Subsequence Discussions | Algorithms | HackerRank
We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
//package solve_problems;/* * 2024 ^_^ *ThinhNguyen97 * */importjava.math.BigInteger;importjava.util.ArrayList;importjava.util.Arrays;importjava.util.Collections;importjava.util.Comparator;importjava.util.HashMap;importjava.util.Set;importjava.util.HashSet;importjava.util.LinkedList;importjava.util.List;importjava.util.Map;importjava.util.Queue;importjava.util.Scanner;importjava.util.Stack;publicclassSolve_problems{staticvoidsolve(int[]X,int[]Y){intn=X.length,m=Y.length;int[][]dp=newint[n+1][m+1];for(inti=0;i<=n;i++)dp[i][0]=0;for(inti=0;i<=m;i++)dp[0][i]=0;for(inti=1;i<=n;i++)for(intj=1;j<=m;j++){if(X[i-1]==Y[j-1])dp[i][j]=dp[i-1][j-1]+1;elsedp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);}// Reconstruct the LCSintlcsLength=dp[n][m];int[]lcs=newint[lcsLength];// Array to hold the LCSintindex=lcsLength-1;inti=n,j=m;while(i>0&&j>0){if(X[i-1]==Y[j-1]){// Current elements match, so they are part of the LCSlcs[index]=X[i-1];i--;j--;index--;}else{// Move to the cell that gives maximum length of LCSif(dp[i-1][j]>dp[i][j-1])i--;elsej--;}}// Print the LCS//System.out.println("Length of Longest Common Subsequence: " + lcsLength);//System.out.print("Longest Common Subsequence: ");for(intk=0;k<lcsLength;k++)System.out.print(lcs[k]+" ");//System.out.println();}publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);////////intn=sc.nextInt(),m=sc.nextInt();int[]X=newint[n];for(inti=0;i<n;i++)X[i]=sc.nextInt();int[]Y=newint[m];for(inti=0;i<m;i++)Y[i]=sc.nextInt();solve(X,Y);// Close the Scanner instancesc.close();}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
The Longest Common Subsequence
You are viewing a single comment's thread. Return to all comments →