asif_iut's blog

Finding the LCS of N strings
By asif_iut, 13 years ago, In English

how to find the Longest Common Subsequence ( LCS ) of  N strings ? is there any dp recurrence ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (22)
| Write comment?
13 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Never mind.

→ Reply
  • 13 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    There is one problem. Let we have 3 strings:

    AAAAAABC
    AAAAAADC
    EEEEEEEFC

    The first step gives us the LCS "AAAAAA" and the second one gives the empty LCS. But the right answer is "C".

    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can be done almost in the same way as for two strings with a suffix automaton. Complexity is O(total length of all strings).
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Can you describe your algo?
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      It is decribed at e-maxx.ru how to solve it for two strings. The only difference is that for each state of the automaton you have to store a bitmask that contains an information about strings that have a substring which ends in this state.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it
        if you say about bit masks, the complexity is not O(total length of all strings), but atleast O(2^ number of strings) .
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it
          It takes O(length of the first string) time to build an automaton and O(total length of all strings) to calculate for each string all states of the automaton that can be reached from this string (that are the substrings of a given string). Actually, bitmask is not necessary, for each state you just have store whether is it still reachable from all processed strings.
          → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
by LCS i mean Longest Common Subsequence.... sorry for not mentioning this before
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    As I know it is NP problem.

    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it -14 Vote: I do not like it

      it can also be done using suffix array but it's not as optimal as suffix automata approach.

      → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    BTW, I don't know anything better than O(multiply of all lengths). And with such complexity there is a simple dp approach.
    → Reply
13 years ago, # |
  Vote: I like it +2 Vote: I do not like it
The problem is NP-hard.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it -16 Vote: I do not like it
    You guys misanderstood what I said. I was talking about
    longest common substring for n strings. As Sergey said longest common subsequence  for n strings is NP.
    Longest common substring as I know it can be solve using suffix array ,suffix tree, or suffix automaton. 
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      The author asked for LCS (subsequence). And I was responding to his post, not yours.

      The NP-hardness can be shown by a reduction to the Vertex Cover problem.

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I know this is old, but can't we find LCS of 2 strings, then find LCS of another 2 strings and so on of every string, then take LCS of 2 LCSes?

Imagine 4 strings, we take LCS of 1&2 and 3&4, whatever LCS we get, we take LCS of them both.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Good day to you,

    well not sure if I understood you correctly, yet, lets imagine following strings:

    aaabb
bbaaa
cccbb
bbccc

    Firstly: LCS(aaabb,bbaaa)==aaa [imho doesn't matter here whether subsequence or substring was meant :P ]

    Secondly LCS(cccbb,bbccc)==ccc

    So we take results LCS(aaa,ccc)==""

    Which shall not be correct if I'm not mistaken, since LCS(aaabb,bbaaa,cccbb,bbccc)=="bb"

    Wish you a nice day!

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks, How about finding the LCS between all strings/sequences and storing the one with minimum length, eg check (1,2)(1,3)(1,4)(2,3)(2,4)and(3,4) here.

      I am new to the world of algorithms, am learning LCS for the first time, it would be of enormous help. Thanks.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Uh, I'm sorry, but I'm afraid I don't understand your algorithm now.

        Mostly part "finding the LONGEST COMMON SUBSTRING/SUBSEQUENCE between all strings/sequences and storing the one with minimum length" — not sure what are we storing in here :'(

        Not sure what you exactly want/expect from an algorithm.

        Anyway as soon you are looking for any interesting algorithms (want to learn, or you are interested in) — for Longest Common Subsequence:

        The most useful (due to its simplicity) is classical dynamic programming which was mentioned by CherryTree above.

        If you would like to go more "deep" (but sorry, I was never thinking about the "generalisation" of these algorithms — so I'll mention it for 2 only), you might be interested in:

        1. DP which reduces complexity to O(N2 + M) insread of O(N * M) (useable for long+short string)

        2. Hunt-Szymanski Algorithm, which is pretty sexy — considering the character layout of strings

        3. LCS using four russians method (at least I guess it is called like this) which is also very sexy (yet imho greater pain :p) which provides awesome speedup, leting us solve "big" subsequences.

        As long as you would be interested in Longest Common Substring, then there is much bigger diversity in order of complexities. I will also talk about LCS for 2 strings, yet HERE it is usually "easily" (or somehow) generalisable:

        1. Obiously, but it is nothing interesting, you can go with some very naive algorithm — for each substring of one string, try whether it is in the other string ... hope I didn't make big mistake but it would be O(N4) (considering both strings to be of size N)? Obviously easily generalised for multiple strings, but the complexity shall not raise significantly (you have more strings.. but the "opponent" shall make them shorter... just polemisation)

        2. There are some "interesting" speedups... for example if you use trie or hashing, you can easily get rid or one N in the complexity. This also isn't interesting, yet imho it is good brain-teaser if you are begginer in this field... since you can "get rid off" another N if you will continue in similar manner.

        3. Here, the first interesting (not fastest, yet imho not hard + kinda easy) method is usage of hashing and Binary Search. Also big "+" of this method is, that it is very easily generalised for multiple strings. The cost is O(Nlog(N)) (and I think it is fairly possible to come up with this idea yourself ^_^ )

        4. Finally, if you would like to go "deeper" or "faster" you could use some suffix data structures. Kinda problem is, that most of them (imho) are not "easy" as you would like to go O(N). An example is usage of Suffix Array + LCP... or something guys above mentioned... again, generalisable to multiple strings.

        Sorry for wall of text. As you are beggined with this topic, I think for topic a, the key is basic dynamic which solves most of the problems one meets and for the second problem imho it is necessary to understand point 3.

        Wish you a Nice Day!

        Good Luck

        ~/Morass

        → Reply