2

アルゴリズムの質問が 1 つあります。

質問は次のとおりです。

文字 A、B、C、D で構成されるタンパク質文字列が与えられます。その中で最小長のシーケンスを見つける必要があります。

例

0 1 2 3 4 5 6 7 8 9 10 11 12
A B A C D C A B C D  C  C  D  

String to find is : BCD 

This string is find between (StartPoint, EndPoint)
1, 4
7, 9
1, 12
7, 12

Minimum length is of 7, 9.

So the answer is 7, 9

私の仕事、

  1. O（n ^ 2）でブルートフォースアプローチを使用してこれを解決できます。
  2. DP を使用して、メイン ストリングに存在する最初のシーケンスを見つけることができます。私の DP ロジックは次のとおりです。
A = Main string
B = String to be find
DP = Dynamic programming function

n = A.size, m = B.size

Build an array of  DP[m+1][n+1]

DP[i][j], means If in A[0...i], B[0...j] is present or not.

This way we can find our first occurence of B in A. Now after this, I am stuck.

あなたの側からのヒントが必要です。

ヒント/ガイダンスのみを提供してください。コードや実装は必要ありません。

4

2 に答える 2

0

例に基づいて、検索文字列を指定された順序で見つける必要があると想定しています (つまりACB、 の有効な検索ではありませんABC)。

一般的な DP アプローチ / ヒント:

最小化しようとしている関数はこれまでの距離であるため、これはマトリックスの各セルに格納されている値である必要があります。

文字列内の特定の位置と検索文字列内の特定の位置について、検索文字列内の 1 つ前の位置について、文字列内の以前のすべての位置を振り返る必要があります。これらすべてについて、そこまでの距離を追加し、最小値を記録する必要があります。

説明のために、検索文字列がA, B, C, D. 次にABC、検索文字列内の for と文字列内の位置について、 forを通してi位置を調べる必要があります。0i-1AB

BACCDstringと search stringが与えられたBCD場合、両方の最後の位置を見ると、次のようになります。

DP(BACCD, BCD) = min(4+DP(B, BC), 3+DP(BA, BC), 2+DP(BAC, BC), 1+DP(BACC, BC))

ただしDP(B, BC)、andDP(BA, BC)は無効であり、BandBAを含まBCず、より具体的には、a で終わらないC(したがって、任意の大きな値を割り当てることができます)。

検索文字列の最後の文字に到達すると、その値は文字列内のその位置で終わる完全な検索文字列が見つかったことを示すため、グローバル最小値と比較する必要があります。

最適化：

O(m*n)実行時間ではなく時間を取得するO(m*n^2)には、現在の文字の別の文字が表示されたらすぐに逆方向の反復を停止できることに注意してください (その時点までのシーケンスは、最後の文字だけが前方に移動した同じシーケンスよりも長いため)。 、つまり:

文字列ABCCDと検索文字列 を指定するとABC、2 番目の をチェックするときに、は よりも短いCため、最初の に到達するとすぐに停止できますC(これはすぐです) 。ABCABCC

サイドノート：

DPアプローチよりもうまくいくと思いますが、ここで何か他のことを提案するとしたら、文字列のすべての文字を含む最小ウィンドウの長さを見つけるへの回答の1つからコピー/インスピレーションを受ける可能性があります別の文字列。

于 2013-10-07T13:31:12.080 に答える
0

サンプルの問題とその解決策は、解決策が常に部分文字列の最初の文字の位置と部分文字列の最後の文字の位置を含む数値のペアになることを明確に示唆しています。

If the substring is BCD, then solution will be position of B, position of D

残りの部分文字列 (この場合は C) がソリューション ペアの間にあるとします。

したがって、ヒントを与えるために、メイン文字列の部分文字列の最初の文字の位置を見つけることから始めて、それらの位置を配列に格納できます。同様に、部分文字列の最後の文字の位置を見つけて配列に格納できます。これにより、配列 2 の数値が配列 1 の数値よりも大きくなるように、配列 1 の 1 つの数値と配列 2 の 1 つの数値で各ペアが構成される可能性のある解セットのセットが得られます。そのようなペアはありません。これは、解決策がないことを意味します。つまり、部分文字列がメイン文字列に存在しないか、そのようなペアが 1 つ以上見つかる可能性があります。つまり、解決策がある可能性があります。あとは、部分文字列の残りが解のペアの間に存在するかどうかを確認するだけです。最後にそのようなペアが複数ある場合は、次に、より高い数値からより低い数値を差し引いた値が適切なソリューションに解決されるはずです。あなたが答え全体を知りたくないと言ったように、これが役に立てば幸いです。あなたはただヒントを探しているだけです:)

于 2013-10-07T13:05:10.417 に答える