I'm looking for pointers to algorithms which will find long connected similar subsequences which two given sequences have in common. For example, in case of two strings:


I'm interested in:


Not in:


(which would be one possible longest common subsequence for the given strings).

For the example above, e represents a (small) difference in the otherwise identical strings UVWXYZ and UVWXeYZ. This is where the similarity comes in. e is not necessarily an addition of a single character. It may be a change as well. When thinking on longer strings, multiple characters (even in direct succession) may be different.

The algorithm should probably be driven by a rating function for the length and the similarity of subsequences.

I'm aware that this problem is rather vague, so any pointers to possibly related problem domains and corresponding algorithms are appreciated as well.

Update: Removed exclusion criterion "LCS", because it actually seems to be what I'm looking for.

  • 1
    $\begingroup$ Are you looking for the longest common substring? en.wikipedia.org/wiki/Longest_common_substring_problem $\endgroup$
    – D.W.
    Sep 20, 2016 at 23:39
  • $\begingroup$ @D.W. thanks for this pointer. I'm pretty sure "longest common substrings with k mismatches" is what I'm looking for. Though my k won't be constant but somehow be related to the substring length. $\endgroup$
    – mstrap
    Sep 21, 2016 at 8:32
  • $\begingroup$ @Evil I meant similarity in a more abstract way. It's pretty much the similarity which e.g. a human would see between two similar sentences. I'm not yet clear on how to formalize this. $\endgroup$
    – mstrap
    Sep 21, 2016 at 8:41
  • 3
    $\begingroup$ You're looking at a special case of sequence alignment: local and with high cost for gaps. $\endgroup$
    – Raphael
    Sep 21, 2016 at 9:38
  • 3
    $\begingroup$ Note that your example is not very descriptive. For instance, since you allow insertions, deletions and mismatches, you can express the match you don't want in these terms as well. You need to specify more precisely what you want "connected" to mean. (I think you have an intuitive notion of a cost function for sequence alignments, but you'll have to solidify that.) $\endgroup$
    – Raphael
    Sep 21, 2016 at 9:41

2 Answers 2


You might be interested in linear-time LCS variant with $k$ mismatches taking gaps with some penalty. Even though the core algorithm is with fixed gaps it is easily converted to your problem by just running algorithm with several gap lengths (naive approach). Better one would be to change the function calculating distance with function over penalties.

Another approach would be to take suffix tree modified to ignore gaps of length at most $k$ and then calculating penalties on the results (starting from longest one and then prunning results based on calculated best so far match including gap penalties). Optimized tree or DAG will decrease the memory footprint.

If you are interested in circular match simply concanate one string with itself.

  • $\begingroup$ Thanks for this idea. From my understanding, the approach of the cited paper is $O(n^2)$. From what I have read until now, there is probably no more efficient solution. Especially, suffix trees won't improve this? From a practical perspective, I'm dealing with sequences with 100 - 1000 tokens on average. Implementation will be in Java. Given that, would you recommend to follow the approach suggested in the paper or would you use suffix trees? $\endgroup$
    – mstrap
    Sep 21, 2016 at 22:13
  • $\begingroup$ @mstrap It depends on gaps (count and length). Suffix trees are good to pursue, it will decrease the average cost. Please check also fast k-mismatch. $\endgroup$
    – Evil
    Sep 22, 2016 at 2:23
  • $\begingroup$ LCS Variant Link is dead. Could you locate the new one or remove it all together. $\endgroup$ Sep 12, 2018 at 12:27
  • $\begingroup$ @Cyclotron3x3 researchgate.net/publication/…, I will look into it later to find not walled version. $\endgroup$
    – Evil
    Sep 12, 2018 at 17:06

Let's call this problem LCCS, which is different with LCS. One straightforward way is to use a brute force algorithm with time complexity $O(nm(n+m))$.

 1. Input: A[1..n], B[1..m] 
 2. Output: Length of the longest common connected subsequence
 3. max = 0
 4. for i from 1 to n
 5.    for j from 1 to m
 6.        if (lowercase(A[i]) = lowercase(B[j]))
 7.           i' = i
 8.           j' = j
 9.           len = 1
 10.          while (i' <= n and j' <= m)
 11.             i'++
 12.             j'++
 13.             if (lowercase(A[i']) != lowercase(B[j'])) break;
 14.             else len++;
 15.          if (len > max) max = len
 16. return max
  • 2
    $\begingroup$ Or use a suffix tree and get $\Theta (n + m)$. There is one problem, how your code detects "Y" -> "y"? It breaks so it returns "UVWX" only as count 4 not 6. $\endgroup$
    – Evil
    Sep 21, 2016 at 4:47
  • 2
    $\begingroup$ @Evil can we just take the lowercase? $\endgroup$
    – orezvani
    Sep 21, 2016 at 5:22
  • 1
    $\begingroup$ Unfortunately, this approach does not account to the similarity. I've updated my question -- sorry for not being precise here. $\endgroup$
    – mstrap
    Sep 21, 2016 at 8:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.