title: Why is the longest common subsequence for multiple strings NP-Hard?
body: <p>I'm having a tough time understanding why the longest common subsequence problem for multiple strings (k > 2) is NP-Hard. I know that the LCS problem for two strings of length l1, l2 can be solved in O(l1*l2) time. My question is why can't we find the LCS of two strings at a time, for example:</p>
  
  <p>LCS(abcd, ad, abc) = LCS(LCS(abcd, ad), abc) = LCS(ad, abc) = a</p>
  
  <p>This algorithm would take O(k*Max_length^2) for k strings. Why is this wrong?</p>