<p>首先,您至少可以通过计算<a href="http://docs.python.org/library/stdtypes.html#set.symmetric_difference" rel="nofollow">set symmetric difference</a>来消除不在两个序列中出现的任何三元组来减少这个问题。在</p>
<p>对于最长的子序列,该算法使用<a href="http://en.wikipedia.org/wiki/Dynamic_programming" rel="nofollow">dynamic programming</a>方法。对于每一个三元组,找出长度为2的最短子串。循环这些对,尝试通过组合这些对来扩展它们。一直延伸,直到每个三元组都有最长的延伸。选择其中最长的:</p>
<pre><code>ABQACBBA
ZBABBA
Eliminate symmetric difference
ABABBA and BABBA
Start with the first A in ABABBA.
It is followed by B, giving the elements [0,1]
Check to see if AB is in BABBA, and record a match at [1,2]
So, the first pair is ((0,1), (1,2))
Next, try the first B in ABABBA.
It is followed by an A giving the elements [1,2]
Check to see if BA is in BABBA and record a match at [0,1]
Continue with the rest of the letters in ABABBA.
Then, try extensions.
The first pair AB at [0,1] and [1,2] can be extended from BA
to ABA [0,1,3] and [1,2,4]. Note, the latter group is all the
way to the right so it cannot be extended farther. ABA cannot
be extended.
Continue until all sequences have extended are far as possible.
Keep only the best of those.
</code></pre>