title: Algorithm: Find all common substrings between two strings where order is preserved
body: <p><strong>Would like to discuss algorithms, no code.</strong></p>
  
  <p><strong>Problem:</strong> Let S and T be two sequences of elements. Find the common subsequences between them where <a href="http://en.wikipedia.org/wiki/Substring" rel="nofollow">the order of the elements is preserved</a>. </p>
  
  <p>It should have O(n + m) running time where n is the length of S, and m is the length of T. I would also like to make the assumption that for the most part the two sequences will be similar.</p>
  
  <p><strong>An optimal solution?:</strong> After some research, one solution that appears to be optimal is to first build a generalised suffix tree for the two sequences. Then find the <a href="http://en.wikipedia.org/wiki/Longest_common_substring_problem" rel="nofollow">longest common substring</a> and consider this subsequence to be part of the solution. Then either remove this subsequence from the tree or build a new suffix tree with this subsequence removed from the two original sequences to form S' and T'. Then find the longest common substring between S' and T', and so on. </p>
  
  <p>To analyze the running time, building the tree takes O(n) and you can find the lengths and starting positions of the longest common substrings of S and T in O(n + m).</p>
  
  <p>Are there other (more) practical solutions that someone knows of or can link to? Any published papers considering the same or related problem you all know about? Input and constructive criticism about the above solution? Thanks for all your time!</p>