2019-05-10

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