Find Longest Common Subsequence
This program finds longest common subsequence between two strings.
Problem Statement
Write a Java program to find longest common subsequence of "Eduinq" and "Enquiry".
Source Code
| 1 | public class LongestCommonSubsequence { |
| 2 | public static void main(String[] args) { |
| 3 | System.out.println("Eduinq Longest Common Subsequence"); |
| 4 | String s1="Eduinq", s2="Enquiry"; |
| 5 | int m=s1.length(), n=s2.length(); |
| 6 | int[][] dp=new int[m+1][n+1]; |
| 7 | for(int i=1;i<=m;i++){ |
| 8 | for(int j=1;j<=n;j++){ |
| 9 | if(s1.charAt(i-1)==s2.charAt(j-1)) |
| 10 | dp[i][j]=1+dp[i-1][j-1]; |
| 11 | else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]); |
| 12 | } |
| 13 | } |
| 14 | System.out.println("Length of LCS = "+dp[m][n]); |
| 15 | } |
| 16 | } |
Program Output
Eduinq Longest Common Subsequence Length of LCS = 3
Explanation
A dynamic programming table stores the length of the common subsequence considered so far, updated by comparing characters and taking the best of extending a match or carrying forward the maximum from neighboring cells, together finding the LCS length.