finding the longest common difference subsequence

Question

for two given sequences say A and B how can one find the length of the longest common difference subsequence in them such that the difference between the adjacent elements in these sequences is same. E.g if

A = {2,4,6,12}

and

B = {4,8,14}

, then the longest common difference between A and B is {2,6,12} and {4,8,14} as the difference in adjacent temrs in both is same i.e.

{4,6}

so the length is 3. Can longest common subsequence be applied here? or what can be the approach to this problem? Thanks.

Ricky Bobby Ricky Bobby · Accepted Answer · 2011-12-07T17:39:39

You can transform your problem, by substracting each element in each list by the smallest element of the list.

For example:

in A you get : min(A) = 2 then A = {0,2,4,10}

in B you get : min(B)=4 then B={0,4,10}

and your problem is now to find the longest common subsequence.

I guess you can find what you need to solve this problem on SO or anywhere on the web :

Wikipedia article on longest subsequence

Hope it helps

EDIT

@Saeed Amiri is right and my answer is true if and only if the smallest element of A and B are in the longest subsequence.

So it gave me a new idea to solve this problem :

Let D(i,j) be the length of the longest subsequence such that its smallest element in A is the ith element of A (sorted) and its smallest element in B is the jth element of B.

then

D(i,j) = | { A-A(i) } intersect {B - B(j) } |

(notation : |A|=card(A))

you need to find the max of D(i,j) over i and j and you know

0<=D(i,j)<=min(|A|-i,|B|-j)

so if you find D(i,j) = min(|A|-i,|B|-j) you don't need to test for i',j' such that min(|A|-i',|B|-j')<= min(|A|-i,|B|-j)

it's not very efficient (in worst case it's O(n*m)) but at least it corrects my mistake.

it should work,

hope it helps

finding the longest common difference subsequence

2 Answers