1
$\begingroup$

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

$\endgroup$
10
  • 4
    $\begingroup$ Why is this tagged with "genetic-algorithms"? $\endgroup$
    – graffe
    Sep 26 '11 at 10:17
  • 3
    $\begingroup$ 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. $\endgroup$ Sep 26 '11 at 11:36
  • 3
    $\begingroup$ @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. $\endgroup$
    – graffe
    Sep 26 '11 at 12:45
  • 1
    $\begingroup$ @mcorley: I think you have a misunderstanding here; genetic algorithms are not the same thing as algorithms for analysing DNA sequences. $\endgroup$ Sep 26 '11 at 16:02
  • 1
    $\begingroup$ 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? $\endgroup$ Sep 26 '11 at 18:23