java - 比较多个子串

Question

我正在尝试编写一个基本的 DNA 测序仪。也就是说，给定两个相同长度的序列，它将输出相同的字符串，最小长度为 3。所以输入

abcdef dfeabc

会回来

1 abc

我不确定如何着手解决这个问题。我可以比较这两个字符串，看看它们是否完全相等。从那里，我可以比较长度为 1 的字符串大小，即如果 dfeabc 包含 abcde。但是，我怎样才能让程序处理所有可能的字符串，最小长度为 3 个字符？一个问题是上面的 length-1 示例，我还必须执行字符串 bcdef 并进行比较。

Answer 1

天真的方法是获取字符串 A 的每个子字符串并查看它是否在字符串 B 中。

这是一种天真的做法:

for ( int i = 0; i < a.length; i++ ) {
   for ( int j = i+1; j <= a.length; j++ ) {
       if (b.contains(a.substring(i, j))) {
           //if longer than last found match, record this match
       }
   }
}

稍微优化的方法是先查看较长的子串，这样第一个匹配的子串必然是最长的。

for ( int length = a.length; length > 0; length-- ) {
     for ( int i = 0; i + length < a.length; i++ ) {
         if ( b.contains(a.substring(i, i+length)) ) {
             //this is the biggest match
         }
     }
}