Basically, its a 2-sequence longest common sub-sequence (LCS) problem.

What's so special?

1: each alphabet only occurs 2 times, one in each sequence, which means with no same alphabet in one sequence.

2: we can execute 2 (or k) "LCS"es at a time, and we want the sum length of the 2 "LCS"es is the maximum.

Take the figure in the link for example.

1: when with only 1 LCS, we would run as 1-2-3-4-5-6, which length is 6.

2: but now, we have 2 LCSes, we can run one as 1-2-3-4-8, the other as 7-5-6, so the sum length is 5+3=8. Clearly, it is the optimal (maximum) in this example.

How can I do this? With multiple LCSes, and want to maximum the sum length of these LCSes?

Is this problem a NP-complete?

Thanks so much!

~~A~~B~~C~~D~~E~~F~~G~~H

A..1............................................

B........2......................................

D.................... 3.........................

E...........................4...................

H.............................................. 8

C..............7................................

F...................................5...........

G........................................6......

![LCS figure][1]

http://img2.ph.126.net/gWr2LnyNTpLmTuqjbRwrcw==/6597825131144291222.jpg