asif_iut's blog

By asif_iut, 12 years ago,

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

• 0

| Write comment?
 12 years ago, # | ← Rev. 2 →   +1 Never mind.
•  12 years ago, # ^ | ← Rev. 3 →   0 There is one problem. Let we have 3 strings:AAAAAABCAAAAAADCEEEEEEEFCThe first step gives us the LCS "AAAAAA" and the second one gives the empty LCS. But the right answer is "C".
•  12 years ago, # ^ |   0 I'm sorry, LCS means Longest Common String or Longest Common Suffix?
•  12 years ago, # ^ |   0 Yes,  you're right. This will fail.
•  12 years ago, # ^ |   0 But if we will support the set of nonexpanding common substrings, it can work.
•  12 years ago, # ^ |   0 I've got your idea, thanks.
 12 years ago, # |   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).
•  12 years ago, # ^ |   0 Can you describe your algo?
•  12 years ago, # ^ |   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.
•  12 years ago, # ^ |   -8 if you say about bit masks, the complexity is not O(total length of all strings), but atleast O(2^ number of strings) .
•  12 years ago, # ^ |   +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.
 12 years ago, # |   0 by LCS i mean Longest Common Subsequence.... sorry for not mentioning this before
•  12 years ago, # ^ | ← Rev. 2 →   0 As I know it is NP problem.
•  12 years ago, # ^ | ← Rev. 2 →   -14 it can also be done using suffix array but it's not as optimal as suffix automata approach.
•  12 years ago, # ^ |   0 BTW, I don't know anything better than O(multiply of all lengths). And with such complexity there is a simple dp approach.
 12 years ago, # |   +2 The problem is NP-hard.
•  12 years ago, # ^ |   -16 You guys misanderstood what I said. I was talking aboutlongest 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.
•  12 years ago, # ^ |   +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.
 » 6 years ago, # |   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.
•  » » 6 years ago, # ^ |   +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)==cccSo 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!
•  » » » 6 years ago, # ^ | ← 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.
•  » » » » 6 years ago, # ^ |   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: DP which reduces complexity to O(N2 + M) insread of O(N * M) (useable for long+short string) Hunt-Szymanski Algorithm, which is pretty sexy — considering the character layout of strings 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: 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) 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. 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 ^_^ ) 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