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

Dynamic programming table stores subsequence lengths. - Characters compared, table updated. - Together finds longest common subsequence. Conclusion: Shows how to find longest common subsequence using DP.

Quick Links to Explore