他の文字列内の最大類似部分文字列を見つける

Question

2つの文字列n1とn2が与えられています。これに加えて、私は数Kを提供されています。

今度は、次のような3つの数 - i、j、lを見つける必要があります。 長さlのn1のインデックスiから始まる部分文字列は、 Kはn2のインデックスjで長さlの部分文字列との不一致です。そして、これはKの相違度で可能な最大部分文字列です。

例では、それが明確にすべきである：
N1 =タブリーズ
N2 =トリノ
K = 2
次いで、出力は次のようになります。
I = 2
J = 1
L = 4
["briz"と "orin"は2つの相違点があるため]

現在のアプローチ：n1の各サブシーケンスに対して、n2の最大共通部分シーケンスを見つけようとしています（atmo st Kミスマッチ）。誰かがより効率的にこれを解決するより良いアプローチですか？私はあなたがLCSのような動的なプログラミングでそれを行うことができると思い

Answer 1

、S1でiにおける

共通（I、J、L、K）=最大サブストラト、（のための長さlを持っており、ほとんどのk個のミスマッチで最初にcommon（i、j、l、0）を計算する必要があります。これは簡単です。すべて1 ≤ F ≤ K-1 & & KF ≤ T ≤ L-1の

：K> 0

STR1なら[iがLTを+] = STR2 [J！単純な存在であることを保証します

common(i,j,l,k) = maximum{common(i,j,l-t-1,k-f) + common(i,j,t,f-1)} 
else 
    common(i,j,l,k) = maximum{common(i,j,l-t,k-f) + common(i,j,t,f)} 

Answer 2

+ LT]

N1 = qertyq

N2 = quertacが

K = 2

アルゴリズム

0,0,6のための複数の解が存在することになる。この場合に何が起こるか溶液？

1,1,5

2,2,4

3,3,3

2,2,2

あなたは私がサイードが正しいと思う問題への唯一の解決策があることを保証している場合、あなたはそれ

Answer 3

を解決するために、動的プログラミングを使用する必要があります

ここには簡単なブルートフォースがあります。 iとjの可能なすべてのペアの長さを計算します。複雑さはO（n1.length * n2）です。長さ*分（n1.length、n2.length））。両方の文字列の長さがnの場合、これはO（n ）です。ここで

for (i = 0; i < n1.length; i++) 
{ 
    for (j = 0; j < n2.length; j++) 
    { 
     errors = 0 
     len = 0 

     while (errors <= k && i+len < n1.length && j+len < n2.length) 
     { 
      if (n1[i+len] != n2[j+len]) errors++ 
      if (errors <= k) len++ 
     } 

     if (len > best) update best 
    } 
} 

その後、正確にk個のエラーでそれを維持（に沿って部分文字列をシフトし、その時にk個のエラーが発生して部分文字列を設定しますが、オフセット、iとjの間のすべての可能なオフセットを通過し、より効率的なソリューションです）、各点の長さを観察する。複雑さはO（（n1.length + n2.length）* min（n1.length、n2.length））です。両方の文字列の長さがnの場合、これはO（n ）です。

for (offset = -n1.length; offset < n2.length; offset++) 
{ 
    // j is equal to (i + offset) 

    start = (offset > 0) ? 0 : -offset 
    stop = min(n1.length, n2.length - offset) 

    errors = 0 
    e = start // e is one past the end of the sequence, so l = e - i 

    for (i = start; i < stop; i++) 
    { 
     // move the end of the substring to maintain exactly k errors 
     while (e < stop && (errors < k || n1[e] == n2[e+offset])) 
     { 
      if (n1[e] != n2[e+offset]) errors++ 
      e++ 
     } 

     if (e - i > best) update best 

     if (n1[i] != n2[i+offset]) errors-- 
    } 
}