Table of Contents
If you want to practice data structure and algorithm programs, you can go through 100+ data structure and algorithm programs.
In this post, we will see how to find the longest common substring in java.
Program
Given two String, find longest common substring.
For example:
String 2: CoreJavaTutorial
Longest common subString is: Java
Solution
Brute force approach
You can solve this problem brute force. Let’s say you are given two String str1 and st2. Length of Str1 be m and length of str2 be n.You can find all substrings of str1 in o(m^2) time then search each of substring in str2, so total complexicity of algorithm will be o(m^2*n).
Dynamic programming solution
You can solve this problem with the help of dynamic programming.Here is simple algorithm.
- Initialize 2D array of m*n named “dp”
- Iterate over str1 in outer loop(Using i)
- Iterate over str2 in inner loop(Using j)
- If str.charAt(i) == str2.charAt(j)
- If i or j=0 then put dp[i][j] = 1
- If i !=0 and j!=0
- dp[i][j] = dp[i-1][j-1] + 1
- Keep the track of max and endIndex in process
- Find substring with the help of endIndex and max.
Here max denotes the size of longest common substring.
Here is simple program to find longest common sustring in java.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
package org.arpit.java2blog; public class LongestCommonSubstringMain { public static void main(String[] args) { String str1="Java2blog"; String str2="CoreJavaTutorial"; LongestCommonSubstringMain lcsMain=new LongestCommonSubstringMain(); System.out.println("String 1: "+str1); System.out.println("String 2: "+str2); System.out.println("Longest common subString is: " +lcsMain.getLongestCommonSubstring(str1, str2)); } public String getLongestCommonSubstring(String str1, String str2){ int m = str1.length(); int n = str2.length(); int max = 0; int[][] dp = new int[m][n]; int endIndex=-1; for(int i=0; i<m; i++){ for(int j=0; j<n; j++){ if(str1.charAt(i) == str2.charAt(j)){ // If first row or column if(i==0 || j==0){ dp[i][j]=1; }else{ // Add 1 to the diagonal value dp[i][j] = dp[i-1][j-1]+1; } if(max < dp[i][j]) { max = dp[i][j]; endIndex=i; } } } } // We want String upto endIndex, we are using endIndex+1 in substring. return str1.substring(endIndex-max+1,endIndex+1); } } |
When you run above program, you will get below output:
String 2: CoreJavaTutorial
Longest common subString is: Java
The time complexity of this algorithm is o(m*n)
That ‘s all about Longest common substring in java.
