title: Finding all common, non-overlapping substrings
body: <p>Given two strings, I would like to identify all common sub-strings from longest to shortest.</p>
  
  <p>I want to remove any "sub-"sub-strings. As an example, any substrings of '1234' would not be included in the match between '12345' and '51234'.</p>
  
  <pre><code>string1 = '51234'
  
  string2 = '12345'
  
  result = ['1234', '5']
  </code></pre>
  
  <p>I was thinking of finding the <a href="https://en.wikipedia.org/wiki/Longest_common_substring_problem" rel="nofollow noreferrer">longest common substring</a>, then recursively finding the longest substring(s) to the left/right. However, I do not want to remove a common substring after found. For example, the result below <em>shares</em> a 6 in the middle:</p>
  
  <pre><code>string1 = '12345623456'
  
  string2 = '623456'
  
  result = ['623456', '23456']
  </code></pre>
  
  <p>Lastly, I need to check one string against a fixed list of thousands of strings. I am unsure if there is a smart step I could take in hashing out all the substrings in these strings.</p>
  
  <p><strong>Previous Answers:</strong></p>
  
  <p>In this <a href="https://stackoverflow.com/questions/34805488/finding-all-the-common-substrings-of-given-two-strings">thread</a>, a dynamic programming solution is found that takes O(nm) time, where n and m are the lengths of the strings. I am interested in a more efficient approach, which would use suffix trees.</p>
  
  <p><strong>Background:</strong> </p>
  
  <p>I am composing song melodies from snippets of melodies. Sometimes, a combination manages to generate a melody matching too many notes in a row of an existing one.</p>
  
  <p>I can use a string similarity measure, such as Edit Distance, but believe that tunes with very small differences to melodies are unique and interesting. Unfortunately, these tunes would have similar levels of similarity to songs that copy many notes of a melody in a row.</p>