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

# | User | Rating |
---|---|---|

1 | Radewoosh | 3759 |

2 | orzdevinwang | 3697 |

3 | jiangly | 3662 |

4 | Benq | 3644 |

5 | -0.5 | 3545 |

6 | ecnerwala | 3505 |

7 | tourist | 3486 |

8 | inaFSTream | 3478 |

9 | maroonrk | 3454 |

10 | Rebelz | 3415 |

# | User | Contrib. |
---|---|---|

1 | adamant | 172 |

2 | awoo | 165 |

2 | nor | 165 |

4 | SecondThread | 164 |

5 | maroonrk | 162 |

5 | BledDest | 162 |

7 | Um_nik | 161 |

8 | -is-this-fft- | 149 |

9 | Geothermal | 146 |

10 | ko_osaga | 142 |

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2023 02:05:31 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Never mind.

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".

As I know it is NP problem.

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

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.

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.

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.

Good day to you,

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

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!

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.

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

Mostly part "finding the

LONGESTCOMMON 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(N^{2}+M) insread ofO(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(N^{4}) (considering both strings to be of sizeN)? 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

Nin 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" anotherNif 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 dynamicwhich solves most of the problems one meets and for the second problem imho it is necessary to understand point3.Wish you a Nice Day!

Good Luck

~/Morass