Question

A subsequence is anything obtained from a sequence by extracting a subset of elements, but keeping them in the same order; the elements of the subsequence need not be contiguous in the original sequence.

Let A[1 .. m] and B[1 .. n] be two arbitrary arrays. A common subsequence of A and B is another sequence that is a subsequence of both A and B. Describe an efficient algorithm to compute the length of the longest common subsequence of A and B in O(n) time.

Answer 1

Let the input sequences are A[0..n-1] and B[0..m-1] of lengths m & n respectively. Following is the recursive implementation of the equal subarrays:

Since common subarray of A[] and B[] must start at some index i and j such that A[i] is equals to B[j]. Let dp[i][j] be the longest common subarray of A[i…] and B[j…].
Therefore, for any index i and j, if A[i] is equals to B[j], then dp[i][j] = dp[i+1][j+1] + 1.
The maximum of all the element in the array dp[][] will give the maximum length of equal subarrays.
For Example:
If the given array A[] = {1, 2, 8, 2, 1} and B[] = {8, 2, 1, 4, 7}. If the characters match at index i and j for the array A[] and B[] respectively, then dp[i][j] will be updated as 1 + dp[i+1][j+1].
Below is the updated dp[][] table for the given array A[] and B[].