title: Finding all the common substrings of given two strings
body: <p>I have come across a problem statement to find the <b>all the common sub-strings between the given two sub-strings </b> such a way that in every case you have to print the longest sub-string. The problem statement is as follows:</p>
  
  <blockquote>
    <p>Write a program to find the common substrings between the two given strings.  However, do not include substrings that are contained within longer common substrings.</p>
    
    <p>For example, given the input strings <code>eatsleepnightxyz</code> and <code>eatsleepabcxyz</code>, the results should be:</p>
    
    <ul>
    <li><code>eatsleep</code> (due to <code><b>eatsleep</b>nightxyz</code> <code><b>eatsleep</b>abcxyz</code>)</li>
    <li><code>xyz</code> (due to <code>eatsleepnight<b>xyz</b></code> <code>eatsleepabc<b>xyz</b></code>)</li>
    <li><code>a</code> (due to <code>e<b>a</b>tsleepnightxyz</code> <code>eatsleep<b>a</b>bcxyz</code>)</li>
    <li><code>t</code> (due to <code>eatsleepnigh<b>t</b>xyz</code> <code>ea<b>t</b>sleepabcxyz</code>)</li>
    </ul>
    
    <p>However, the result set should <em>not</em> include <code>e</code> from
    <code><b>e</b>atsleepnightxyz</code> <code>eatsl<b>e</b>epabcxyz</code>, because both <code>e</code>s are already contained in the <code>eatsleep</code> mentioned above.  Nor should you include <code>ea</code>, <code>eat</code>, <code>ats</code>, etc., as those are also all covered by <code>eatsleep</code>.</p>
    
    <p>In this, you don't have to make use of String utility methods like: contains, indexOf, StringTokenizer, split and replace.</p>
  </blockquote>
  
  <p>My Algorithm is as follows: I am starting with brute force and will switch to more optimized solution when I improve my basic understanding.</p>
  
  <pre><code> For String S1:
       Find all the substrings of S1 of all the lengths
       While doing so: Check if it is also a substring of 
       S2.
  </code></pre>
  
  <p>Attempt to figure out the time complexity of my approach.</p>
  
  <p><b>Let the two given strings be n1-String and n2-String </b></p>
  
  <ol>
  <li>The number of substrings of S1 is clearly n1(n1+1)/2. </li>
  <li>But we have got to find the average length a substring of S1. </li>
  <li>Let’s say it is m. We’ll find m separately.</li>
  <li>Time Complexity to check whether an m-String is a substring of an
  n-String is O(n*m).</li>
  <li>Now, we are checking for each m-String is a substring of S2,
  which is an n2-String. </li>
  <li>This, as we have seen above, is an O(n<sup>2</sup> m) algorithm.</li>
  <li>The time required by the overall algorithm then is </li>
  <li>Tn=(Number of substrings in S1) * (average substring lengthtime for character comparison procedure)</li>
  <li>By performing certain calculations, I came to conclusion that the
  time complexity is O(n<sup>3</sup> m<sup>2</sup>) </li>
  <li>Now, our job is to find m in terms of n1.</li>
  </ol>
  
  <p><b>Attempt to find m in terms of n1.</b></p>
  
  <p>T<sub>n</sub> = (n)(1) + (n-1)(2) + (n-2)(3) + ..... + (2)(n-1) + (1)(n)<br>
  where T<sub>n</sub> is the sum of lengths of all the substrings.</p>
  
  <p>Average will be the division of this sum by the total number of Substrings produced.</p>
  
  <p>This, simply is a summation and division problem whose solution is as follows O(n)</p>
  
  <p><b>Therefore...</b></p>
  
  <p>Running time of my algorithm is O(n^5).</p>
  
  <p>With this in mind I wrote the following code:</p>
  
  <pre><code> package pack.common.substrings;
  
   import java.util.ArrayList;
   import java.util.LinkedHashSet;
   import java.util.List;
   import java.util.Set;
  
   public class FindCommon2 {
      public static final Set&lt;String&gt; commonSubstrings = new      LinkedHashSet&lt;String&gt;();
  
   public static void main(String[] args) {
      printCommonSubstrings("neerajisgreat", "neerajisnotgreat");
      System.out.println(commonSubstrings);
  }
  
   public static void printCommonSubstrings(String s1, String s2) {
      for (int i = 0; i &lt; s1.length();) {
          List&lt;String&gt; list = new ArrayList&lt;String&gt;();
          for (int j = i; j &lt; s1.length(); j++) {
              String subStr = s1.substring(i, j + 1);
              if (isSubstring(subStr, s2)) {
                  list.add(subStr);
              }
          }
          if (!list.isEmpty()) {
              String s = list.get(list.size() - 1);
              commonSubstrings.add(s);
              i += s.length();
          }
      }
   }
  
   public static boolean isSubstring(String s1, String s2) {
      boolean isSubstring = true;
      int strLen = s2.length();
      int strToCheckLen = s1.length();
      if (strToCheckLen &gt; strLen) {
          isSubstring = false;
      } else {
          for (int i = 0; i &lt;= (strLen - strToCheckLen); i++) {
              int index = i;
              int startingIndex = i;
              for (int j = 0; j &lt; strToCheckLen; j++) {
                  if (!(s1.charAt(j) == s2.charAt(index))) {
                      break;
                  } else {
                      index++;
                  }
              }
              if ((index - startingIndex) &lt; strToCheckLen) {
                  isSubstring = false;
              } else {
                  isSubstring = true;
                  break;
              }
          }
      }
      return isSubstring;
   }
  }
  </code></pre>
  
  <p>Explanation for my code:</p>
  
  <pre><code> printCommonSubstrings: Finds all the substrings of S1 and 
                          checks if it is also a substring of 
                          S2.
   isSubstring : As the name suggests, it checks if the given string 
                 is a substring of the other string.
  </code></pre>
  
  <p>Issue: Given the inputs</p>
  
  <pre><code>  S1 = “neerajisgreat”;
    S2 = “neerajisnotgreat”
    S3 = “rajeatneerajisnotgreat”
  </code></pre>
  
  <p>In case of S1 and S2, the output should be: <code>neerajis</code> and <code>great</code>
  but in case of S1 and S3, the output should have been: 
  <code>neerajis</code>, <code>raj</code>, <code>great</code>, <code>eat</code> but still I am getting <code>neerajis</code> and <code>great</code> as output. I need to figure this out.</p>
  
  <p>How should I design my code?</p>