Find the longest sequence S, which is a subsequence of the string A, B, C

Question

Give a polynomial time algorithm that takes three lines, A, B, and C, as input, and returns the longest sequence S, which is a subsequence of A, B, and C.

Answer 1

Let dp[i, j, k] = longest common subsequence of prefixes A[1..i], B[1..j], C[1..k]

We have:

 dp[i, j, k] = dp[i - 1, j - 1, k - 1] + 1 if A[i] = B[j] = C[k] max(dp[i - 1, j, k], dp[i, j - 1, k], dp[i, j, k - 1]) otherwise 

As in the case of 2d, except for three dimensions. Complexity O(len A * len B * len C) .

Answer 2

Here's a solution in Python for an arbitrary number of sequences. You can use it to test your solution for 2D, 3D enclosures. He closely follows the Wikipedia algorithm :

 #!/usr/bin/env python import functools from itertools import starmap @memoize def lcs(*seqs): """Find longest common subsequence of `seqs` sequences. Complexity: O(len(seqs)*min(seqs, key=len)*reduce(mul,map(len,seqs))) """ if not all(seqs): return () # at least one sequence is empty heads, tails = zip(*[(seq[0], seq[1:]) for seq in seqs]) if all(heads[0] == h for h in heads): # all seqs start with the same element return (heads[0],) + lcs(*tails) return max(starmap(lcs, (seqs[:i]+(tails[i],)+seqs[i+1:] for i in xrange(len(seqs)))), key=len) def memoize(func): cache = {} @functools.wraps(func) def wrapper(*args): try: return cache[args] except KeyError: r = cache[args] = func(*args) return r return wrapper 

Note: without memoization, this is an exponential algorithm ( wolfram alpha ):

 $ RSolve[{a[n] == K a[n-1] + K, a[0] = K}, a[n], n] a(n) = (K^(n + 1) - 1) K/(K - 1) 

where K == len(seqs) and n == max(map(len, seqs))

Examples

 >>> lcs("agcat", "gac") ('g', 'a') >>> lcs("banana", "atana") ('a', 'a', 'n', 'a') >>> lcs("abc", "acb") ('a', 'c') >>> lcs("XMJYAUZ", "MZJAWXU") ('M', 'J', 'A', 'U') >>> lcs("XMJYAUZ") ('X', 'M', 'J', 'Y', 'A', 'U', 'Z') >>> lcs("XMJYAUZ", "MZJAWXU", "AMBCJDEFAGHI") ('M', 'J', 'A') >>> lcs("XMJYAUZ", "MZJAWXU", "AMBCJDEFAGUHI", "ZYXJAQRU") ('J', 'A', 'U') >>> lcs() #doctest: +IGNORE_EXCEPTION_DETAIL Traceback (most recent call last): ... ValueError: >>> lcs(*"abecd acbed".split()) ('a', 'b', 'e', 'd') >>> lcs("acd", lcs("abecd", "acbed")) ('a', 'd') >>> lcs(*"abecd acbed acd".split()) ('a', 'c', 'd') 

Answer 3

All you have to do is Google’s “longest subsequence”.

This is the top link: http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

If you have a specific problem, understanding this, please ask here, preferably with a more specific question.