Is it possible to find longest common subsequence of n sequences n<=1000

1

k=length of each sequence
n=no of sequences
eg-
k=4
n=4
ABCD
BDAC
ABDC
BACD
ans is AC, BD

2

If the lengths of the strings are quite small (or equally, the number of strings if not), then yes it is possible. The dynamic programming algorithm for N strings is O(N * n1 * n2 * … * nN ) where ni is the length of the i’th string. Given N \le 1000, the strings don’t have much independence to have a larger length as that would make the problem intractable (which is what it really is for an arbitrary number of strings) :slightly_smiling_face:

3

Yes but for n=500 it won’t work XD

4

if all the subsequences are just permutations of the same string and the length is less enough, then you can apply DFS and find the longest path in the graph consisting of the elements of the sequence, and there’s an edge (i,j), if j is greater than i in each of the sequence.

See this problem and tutorial for reference

1 Like