Longest Common Substring

This program finds longest common substring using dynamic programming.

Problem Statement

Write a Java program to find longest common substring of "Eduinq" and "Enquiry".

Source Code

1 public class LongestCommonSubstring {
2 public static void main(String[] args) {
3 System.out.println("Eduinq Longest Common Substring");
4 String s1="Eduinq", s2="Enquiry";
5 int m=s1.length(), n=s2.length();
6 int[][] dp=new int[m+1][n+1];
7 int maxLen=0, endIndex=0;
8 for(int i=1;i<=m;i++){
9 for(int j=1;j<=n;j++){
10 if(s1.charAt(i-1)==s2.charAt(j-1)){
11 dp[i][j]=dp[i-1][j-1]+1;
12 if(dp[i][j]>maxLen){
13 maxLen=dp[i][j];
14 endIndex=i;
15 }
16 }
17 }
18 }
19 System.out.println("Longest common substring: "+s1.substring(endIndex-maxLen,endIndex));
20 }
21 }

Program Output

Eduinq Longest Common Substring
Longest common substring: ui

Explanation

DP table tracks substring matches. - Maximum length updated when characters match. - Together finds longest common substring. Conclusion: Shows how to find longest common substring using DP.

Quick Links to Explore