Блог пользователя asif_iut

Finding the LCS of N strings
Автор asif_iut, 13 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Never mind.

→ Ответить
13 лет назад, # |
← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

If I have right idea, this not this task can be solved by suffix array with complexity about O(S log S), where S is sum of all string's lengths.

Looks truly and very simple, so I'll share.
Build suffix array of concatenation of all strings.
Go for all elements with two links, that mean begin and end point of curent segment. Also keep LCP of all consecutive suffixes(in heap for example).
If suffixes in curent segment belong to all N strings, then check minimum element of the heap for answer and decrease length of segment(move left link). In other case, increase length of segment(move right link).
No gurantee, may be I'm wrong.

→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can be done almost in the same way as for two strings with a suffix automaton. Complexity is O(total length of all strings).
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Can you describe your algo?
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      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.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится
        if you say about bit masks, the complexity is not O(total length of all strings), but atleast O(2^ number of strings) .
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          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.
          → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
by LCS i mean Longest Common Subsequence.... sorry for not mentioning this before
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
The problem is NP-hard.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится -16 Проголосовать: не нравится
    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. 
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

      → Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    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!

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

        → Ответить