2

基本的な DNA シーケンサーを作成しようとしています。その中で、同じ長さの 2 つのシーケンスが与えられると、最小長が 3 の同じ文字列が出力されます。

abcdef dfeabc

戻ります

1 abc

問題を解決する方法がわかりません。2 つの文字列を比較して、それらが完全に等しいかどうかを確認できます。そこから、長さ 1 の文字列サイズを比較できdfeabcますabcde。ただし、最小サイズの 3 文字まで、考えられるすべての文字列をプログラムに実行させるにはどうすればよいでしょうか? 1 つの問題は、長さ 1 の上記の例です。文字列 bcdef も実行して比較する必要があります。

4

3 に答える 3

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
         }
     }
}
于 2010-09-29T19:31:18.633 に答える
0

これを単純な方法で解決したい場合、検索に Java API を使用しない場合、次のように考えることができます:一方、最初の文字列と 2 番目の文字列の対応する文字は等しく、少なくとも 3 つの手順を実行した場合に結果を返します。

于 2010-09-29T19:32:57.090 に答える
0

動的計画問題である、Longest Common Substring アルゴリズムを使用する必要があります。アルゴリズムの説明についてはウィキペディアのエントリを確認し、サンプル実装についてはこちらを確認してください。

于 2010-09-29T19:55:23.180 に答える