title: Longest common subsequence of 3+ strings
body: <p>I am trying to find the longest common subsequence of 3 or more strings. The Wikipedia article has a great description of <a href="http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Solution_for_two_sequences" rel="noreferrer">how to do this for 2 strings</a>, but I'm a little unsure of how to extend this to 3 or more strings.</p>
  
  <p>There are plenty of libraries for finding the LCS of 2 strings, so I'd like to use one of them if possible. If I have 3 strings A, B and C, is it valid to find the LCS of A and B as X, and then find the LCS of X and C, or is this the wrong way to do it?</p>
  
  <p>I've implemented it in Python as follows:</p>
  
  <pre><code>import difflib
  
  def lcs(str1, str2):
      sm = difflib.SequenceMatcher()
      sm.set_seqs(str1, str2)
      matching_blocks = [str1[m.a:m.a+m.size] for m in sm.get_matching_blocks()]
      return "".join(matching_blocks)
  
  print reduce(lcs, ['abacbdab', 'bdcaba', 'cbacaa'])
  </code></pre>
  
  <p>This outputs "ba", however it should be "baa".</p>