algorithmcomputer-sciencepseudocodelcs

longest common subsequence in 3 strings in this way LCS(LCS(string ,string),string)

suppose we want to find LCS for 3 strings. Does finding the LCS (LCS(string,x, string y), string z) give the right solution?

Solution

  • No it is not.

    With this counter example:
    x = 'baa', y = 'aab', z = 'b' you can see that lcs(x, y, z) = 'b', and that lcs(lcs(x, y), z) = lcs('aa', 'b') = ''.

    As a side note, while finding a LCS between two strings can be done in polynomial time, the problem of finding a commom LCS between an arbitrary number of strings is NP-hard.