# Longest substring (for sequences of triplets)

I am trying to compare strings of the format: AAA-ABC-LAP-ASZ-ASK; basically, triplets of letters separated by dashes.

I'm trying to find between 2 such sequences of arbitrary length (from 1 to 30 triplets) the longest sequence of common triplets.

For example, AAA-BBB-CCC-AAA-DDD-EEE-BBB and BBB-AAA-DDD-EEE-BBB, you can find a sequence of 5 (BBB-AAA-DDD-EEE-BBB, even if CCC is not present in the 2nd sequence).

The dashes should not be considered for comparison; they only serve to separate the triplets.

I'm using Python but just a general algorithm to achieve this should do :)

-

As a start, you can at least reduce the problem by computing the set symmetric difference to eliminate any triplets that do not occur in both sequences.

For the longest subsequence, the algorithm uses a dynamic programming approach. For each triplet, find the shortest substring of length two that occurs in both. Loop over those pairs, trying to extend them by combining the pairs. Keep extending until you have all the longest extensions for each triplet. Pick the longest of those:

``````ABQACBBA
ZBABBA

Eliminate symmetric difference
ABABBA and BABBA

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.
``````
-

Sequence alignment algorithms, that are commonly used in bio-informatics, could be used here. They are mostly used to align one-character sequences but they can be modified to accept n-character sequences. Needleman–Wunsch algorithm is one that is fairly efficient.

-
I think that this is the wrong algorithm here. The goal isn't to align the sequences as much as extract the longest common subsequence. Sequence alignment algorithms run less efficiently than the LCS algorithm, and I think that the resulting solution from the sequence alignment algorithm might not map back nicely to what the OP wants. –  templatetypedef Dec 19 '11 at 19:23
@templatetypedef: I agree. Alignment is a more general approach to the particular problem than what is needed. That is why I upvoted your solution :). Though I left mine in case he needs more detailed approach. –  Avaris Dec 19 '11 at 20:50

I think that you're looking for the Longest Common Subsequence algorithm, which can find this sequence extremely quickly (in O(n2) time). The algorithm is based on a simple dynamic programming recurrence, and there are many examples online of how you might implement the algorithm.

Intuitively, the algorithm works using the following recursive decomposition that works by looking at the first triplet of each sequence:

• If either sequence is empty, the longest common subsequence is the empty sequence.
• Otherwise:
• If the first triplets of each sequence match, the LCS is that element followed by the LCS of the remainders of the two sequences.
• If not, the LCS is the longer of the following: the LCS of the first sequence and all but the first element of the second sequence, or the LCS of the second sequence and all but the first element of the first sequence.

Hope this helps!

-
Look like its what I need, I only need to adapt the algorithm to process lists of strings instead of strings I guess :) –  user1106544 Dec 20 '11 at 1:32
@user1106544- You actually don't need to do that much adaptation. If you treat the triplets as the elements of the sequence, the algorithm will work as advertised without any modifications. –  templatetypedef Dec 21 '11 at 0:21
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}