Friday, May 10, 2019

How do you find longest common substring ?

Problem statement:
Given two strings S1 & S2. Find the longest common substring between S1 & S2.
  1. import java.util.ArrayList;
  2. import java.util.List;

  3. public class LongestCommonSubstring {
  4.     public static void main(String[] args) {
  5.         String S1 = "LCLC";
  6.         String S2 = "CLCL";
  7.         //String S3 = "abcdabccab";
  8.         //String S4 = "bcdaccabaabc";
  9.         List<String> com = commonSubstring(S1, S2);
  10.         for (String s: com){
  11.             System.out.println(s);
  12.         }
  13.     }
  14.     public static List<String> commonSubstring(String s1, String s2) {
  15.         Integer match[][] = new Integer[s1.length()][s2.length()];
  16.         int len1 = s1.length();
  17.         int len2 = s2.length();
  18.         int max = Integer.MIN_VALUE;    // max length of the string
  19.         ArrayList<String> result = null;    // result list
  20.         for (int i = 0; i < len1; i++) {    // row iteration
  21.             for (int j = 0; j < len2; j++) {  // column iteration
  22.                 if (s1.charAt(i) == s2.charAt(j)) {
  23.                     if (i == 0 || j == 0)
  24.                         match[i][j] = 1;
  25.                     else
  26.                         match[i][j] = match[i - 1][j - 1] + 1;
  27.                     // if you find a longer common substring re-initialize 
  28. // the max count and update the result list
  29.                     if (match[i][j] > max) {
  30.                         max = match[i][j];
  31.                         result = new ArrayList<String>();
  32.                         // substring starts at i-max+1 & ends at i
  33.                         result.add(s1.substring(i - max + 1, i + 1));
  34.                     }
  35.    // else if you find a common substring with the max length, 
  36.   // store it in the list
  37.                     else if (match[i][j] == max) {
  38.                         result.add(s1.substring(i - max + 1, i + 1));
  39.                     }
  40.                 } else {
  41.                     match[i][j] = 0;
  42.                 }
  43.             }
  44.         }
  45.         return result;
  46.     }
  47. }
Output:
LCL
CLC

No comments:

Post a Comment

How to run standalone mock server on local laptop

 Please download the standalone wiremock server from Direct download section at the bottom of the page.  Download and installation Feel fre...