<p>Depending on your application (and assuming I have correctly understood your general aim), a standard practical method will be to find all maximal repeated substrings between the two strings, number those substrings and then compute the longest increasing subsequence.  This is exactly what the bioinformatics tool Reputer does. See <a href="http://bibiserv.techfak.uni-bielefeld.de/reputer/" rel="nofollow">http://bibiserv.techfak.uni-bielefeld.de/reputer/</a> and 
<a href="http://bioinformatics.oxfordjournals.org/content/15/5/426" rel="nofollow">http://bioinformatics.oxfordjournals.org/content/15/5/426</a> for an original reference.</p>

<p>This is is slightly super-linear time overall as you have to compute the longest increasing subsquence (see e.g. <a href="http://en.wikipedia.org/wiki/Longest_increasing_subsequence" rel="nofollow">http://en.wikipedia.org/wiki/Longest_increasing_subsequence</a> ).</p>

CC BY-SA 3.0
2011-09-26T19:46:25.890Z
I apologize, this is actually a great paper and I am looking further into this.
mcorley
CC BY-SA 3.0
2011-09-26T08:09:12.303Z
2011-09-26T10:16:06.687Z
2011-09-26T10:16:06.687Z
Simd
<p>Consider two strings, S and T. Find the first k longest common non-overlapping substrings of S and T.</p>

CC BY-SA 3.0
2011-09-26T10:17:08.510Z
Why is this tagged with "genetic-algorithms"?
Simd
CC BY-SA 3.0
2011-09-26T11:36:35.050Z
There seems to be some confusion: the title mentions "substrings" but the body of the question mentions "subsequences". Either way, I do not quite understand what is the goal (what should be the output): the set of *all* common substrings or subsequences can very large; you cannot expect a linear-time algorithm.
Jukka Suomela
CC BY-SA 3.0
2011-09-26T12:45:13.630Z
@mcorley, could you clarify if the answer I gave below is what you were looking for and if not, what exactly you would like the output to be, please.
Simd
CC BY-SA 3.0
2011-09-26T15:45:08.820Z
@RaphaelClifford Some genetic algorithms have the same goal when looking at dna sequences and it was the closest tag I found without creating my own.
mcorley
CC BY-SA 3.0
2011-09-26T15:47:28.660Z
@JukkaSuomela Sorry, I have corrected the problem. I mentioned substrings in the title and subsequences where the order of the elements is preserved in the body, which I thought of as the same but I can see a confusion
mcorley
CC BY-SA 3.0
2011-09-26T16:02:00.833Z
@mcorley: I think you have a misunderstanding here; [genetic algorithms](http://en.wikipedia.org/wiki/Genetic_algorithm) are not the same thing as algorithms for analysing DNA sequences.
Jukka Suomela
CC BY-SA 3.0
2011-09-26T16:11:59.190Z
@JukkaSuomela: Ha sorry was late when I posted that is what I took it for. The string-matching tag is much more appropriate. I'll do a better job with my tagging in the future, and have removed the genetic tag. Thanks!
mcorley
CC BY-SA 3.0
2011-09-26T18:23:55.267Z
Unfortunately, the clarification does not yet help much. Consider, for example, the case of strings CDEFACFH and ACDEFH. Now what are the common substrings? (CDEF,H)? (CDE,FH)? (AC,FH)? Something else?
Jukka Suomela
CC BY-SA 3.0
2011-09-26T18:29:56.673Z
Substrings of the longest substring might be among the $k$ longest substrings, so deleting it from the suffix tree is not a good idea. Why not just find the $k$ longest common paths between both suffix trees?
Raphael
CC BY-SA 3.0
2011-09-26T18:35:22.220Z
So if this were the case, I would like to first find the longest common substring, (CDEF), then the second longest, ...., however in this case after finding the first longest it doesn't make sense to continue because the size of the remaining substrings is so small so we would stop here and consider k to be 1.
mcorley
<ds.algorithms><string-matching><string-search>
Algorithm: Find the first k longest substrings between two similar strings
mcorley
# Algorithm: Find the first k longest substrings between two similar strings

(Asked by: username_0 on 2011-09-26)

Consider two strings, S and T. Find the first k longest common non-overlapping substrings of S and T.

**Tags:** ds.algorithms, string-matching, string-search

> **Comments:**
> **username_1**: Why is this tagged with "genetic-algorithms"?  
> **username_2**: There seems to be some confusion: the title mentions "substrings" but the body of the question mentions "subsequences". Either way, I do not quite understand what is the goal (what should be the output): the set of *all* common substrings or subsequences can very large; you cannot expect a linear-time algorithm.  
> **username_1**: @username_0, could you clarify if the answer I gave below is what you were looking for and if not, what exactly you would like the output to be, please.  
> **username_0**: @username_3Clifford Some genetic algorithms have the same goal when looking at dna sequences and it was the closest tag I found without creating my own.  
> **username_0**: @JukkaSuomela Sorry, I have corrected the problem. I mentioned substrings in the title and subsequences where the order of the elements is preserved in the body, which I thought of as the same but I can see a confusion  
> **username_2**: @username_0: I think you have a misunderstanding here; [genetic algorithms](http://en.wikipedia.org/wiki/Genetic_algorithm) are not the same thing as algorithms for analysing DNA sequences.  
> **username_0**: @JukkaSuomela: Ha sorry was late when I posted that is what I took it for. The string-matching tag is much more appropriate. I'll do a better job with my tagging in the future, and have removed the genetic tag. Thanks!  
> **username_2**: Unfortunately, the clarification does not yet help much. Consider, for example, the case of strings CDEFACFH and ACDEFH. Now what are the common substrings? (CDEF,H)? (CDE,FH)? (AC,FH)? Something else?  
> **username_3**: Substrings of the longest substring might be among the $k$ longest substrings, so deleting it from the suffix tree is not a good idea. Why not just find the $k$ longest common paths between both suffix trees?  
> **username_0**: So if this were the case, I would like to first find the longest common substring, (CDEF), then the second longest, ...., however in this case after finding the first longest it doesn't make sense to continue because the size of the remaining substrings is so small so we would stop here and consider k to be 1.  

---

## 1 answers

### Answer by username_1 on 2011-09-26. Score: 4 | Accepted answer

Depending on your application (and assuming I have correctly understood your general aim), a standard practical method will be to find all maximal repeated substrings between the two strings, number those substrings and then compute the longest increasing subsequence. This is exactly what the bioinformatics tool Reputer does. See <http://bibiserv.techfak.uni-bielefeld.de/reputer/> and
<http://bioinformatics.oxfordjournals.org/content/15/5/426> for an original reference.

This is is slightly super-linear time overall as you have to compute the longest increasing subsquence (see e.g. <http://en.wikipedia.org/wiki/Longest_increasing_subsequence> ).

> **Comments:**
> **username_0**: I apologize, this is actually a great paper and I am looking further into this.  

---

