文字列と動的プログラミングアルゴリズム

Question

文字列Zは、ZがXとYの部分文字列を順に連結した場合、2つの他の文字列XとYのマージです。たとえば、 "strMERINGGE"は "string"と "MERGE"のマージです。 3つの文字列を受け取り、3つ目が最初の2つのマージであるかどうかをテストする動的プログラミングアルゴリズムを提供します。

この問題は、最も長い共通サブシーケンス問題のバリエーションのように見えますが、私はこのアルゴリズムを試しましたが、私はそれについてはわかりません。

public static String concat(String s1, String s2) { 
if (string.IsNullOrEmpty(s1)) 
    return s2; 
if (string.IsNullOrEmpty(s2)) 
    return s1; 



int len1 = s1.Length - 1; 
char last1 = s1[len1]; 
char first2 = s2[0]; 


    if (s1[len1 - indexOfLast2] == first2) 
    { 

int inLast2 = s2.LastIn(last1, Math.Min(len1, s2.Length - 1)); 
while (inLast2 != -1) 
{ 
     int x = inLast2; 
     while ((x != -1) && (s1[len1 - inLast2 + x] == s2[x])) 
      x--; 
     if (x == -1) 
      return s1 + s2.Substring(Last2 + 1); 
    } 
inLast2 = s2.LastIn(last1, inLast2 - 1); 

} 


if (s1 + s2.Substring(Last2 + 1) == 2) 
return inLast2 +1; 

Answer 1

私はあなたのものを通過していませんが、実際にはこれはLCSアルゴリズムで解決できると感じています。本当にあなたが見つけるために必要なものです：

• は、LCS（Z、Y）です== Y
• LCS（Z、X）== X
• は、ソート（X + Y）==ですソートされたトリックを行うようだ（Z）

直感的に...

Answer 2

は、それは私には最長共通サブシーケンスより編集距離アルゴリズムに類似聞こえます。

XとYの長さがmとnの場合、（m + 1）×（n + 1）の行列を作成します。現在の文字がX [j]の場合はセル（i、j）=（0,0）、トラバースZ、および1つ右のセル（j + 1）を移動し、1つ下の（i + 1）現在の文字はY [i]と等しくなります。セル（m + 1、n + 1）で終わると真を出力し、いずれかの文字列の文字と一致しないか、他のセルで終わる場合はfalseを返します。非常に類似している編集距離アルゴリズムについて

、参照：http://en.wikipedia.org/wiki/Levenshtein_distance

Answer 3

用途この動的プログラミング再帰：

マッチ（I、J）=マッチ（I-1、j）および（Z

これは、2次元の2進マトリックスを与える。終点と始点の間にパス（連続した真、唯一の上か左、横でない）がある場合、解決策があります（ソリューションはXまで変換し、Yをマッチさせることによって与えられます）。

PS：次の関数を使用して、行列が自動的にパスを覚えているでしょう：この質問の

Match(i,j) = 
    if Match(i-1,j) AND (Z[i+j] == X[i]): 
     1 
    elif Match(i,j-1) AND (Z[i+j] == Y[j]): 
     2 
    else: 
     0