3つの文字列の中で最も長い共通部分シーケンス

Question

私は2つの文字列の中で最も長い共通部分列を見つけるために動的プログラミングソリューションを実装しました。 LCSを3つの文字列の中から見つけるためにこのアルゴリズムを一般化する方法は明らかですが、私の研究ではこれについてどうやって情報を得ることができませんでした。どんな助けもありがとう。

Answer 1

漸化関係を一般化します。

dp[i, j, k] = 1 + dp[i - 1, j - 1, k - 1] if A[i] = B[j] = C[k] 
       max(dp[i - 1, j, k], dp[i, j - 1, k], dp[i, j, k - 1]) otherwise 

答えは、同様の質問hereから撮影された：3つの文字列の場合

。

Answer 2

2つの文字列AとBの最長共通部分列（LCS）を見つけるには、2次元配列を斜めに横断することができます。配列内のすべての要素は、部分文字列A 'とB'（行番号で切り捨てられたA、列番号で切り捨てられたB）のLCSを見つける問題に対応します。この問題は、配列内のすべての要素の値を計算することで解決できます。配列要素の値を計算するときには、与えられた値を計算するために必要なすべてのサブ問題が既に解決されていることを確認しておく必要があります。 2次元配列を斜めに横切るのはそのためです。

この解決策は、N個の文字列間で最も長い共通部分列を見つけるためにスケールすることができますが、これはN次元の配列を反復する必要があります。解決されました。

N次元配列を特別な順序で反復する代わりに、再帰的に問題を解決することもできます。再帰を使用すると、多くのブランチで同じ中間ソリューションが必要になるため、中間ソリューションを保存することが重要です。私はこれを行うC＃で小さな例を書いた：

string lcs(string[] strings) 
{ 
    if (strings.Length == 0) 
     return ""; 
    if (strings.Length == 1) 
     return strings[0]; 
    int max = -1; 
    int cacheSize = 1; 
    for (int i = 0; i < strings.Length; i++) 
    { 
     cacheSize *= strings[i].Length; 
     if (strings[i].Length > max) 
      max = strings[i].Length; 
    } 
    string[] cache = new string[cacheSize]; 
    int[] indexes = new int[strings.Length]; 
    for (int i = 0; i < indexes.Length; i++) 
     indexes[i] = strings[i].Length - 1; 
    return lcsBack(strings, indexes, cache); 
} 
string lcsBack(string[] strings, int[] indexes, string[] cache) 
{ 
    for (int i = 0; i < indexes.Length; i++) 
     if (indexes[i] == -1) 
      return ""; 
    bool match = true; 
    for (int i = 1; i < indexes.Length; i++) 
    { 
     if (strings[0][indexes[0]] != strings[i][indexes[i]]) 
     { 
      match = false; 
      break; 
     } 
    } 
    if (match) 
    { 
     int[] newIndexes = new int[indexes.Length]; 
     for (int i = 0; i < indexes.Length; i++) 
      newIndexes[i] = indexes[i] - 1; 
     string result = lcsBack(strings, newIndexes, cache) + strings[0][indexes[0]]; 
     cache[calcCachePos(indexes, strings)] = result; 
     return result; 
    } 
    else 
    { 
     string[] subStrings = new string[strings.Length]; 
     for (int i = 0; i < strings.Length; i++) 
     { 
      if (indexes[i] <= 0) 
       subStrings[i] = ""; 
      else 
      { 
       int[] newIndexes = new int[indexes.Length]; 
       for (int j = 0; j < indexes.Length; j++) 
        newIndexes[j] = indexes[j]; 
       newIndexes[i]--; 
       int cachePos = calcCachePos(newIndexes, strings); 
       if (cache[cachePos] == null) 
        subStrings[i] = lcsBack(strings, newIndexes, cache); 
       else 
        subStrings[i] = cache[cachePos]; 
      } 
     } 
     string longestString = ""; 
     int longestLength = 0; 
     for (int i = 0; i < subStrings.Length; i++) 
     { 
      if (subStrings[i].Length > longestLength) 
      { 
       longestString = subStrings[i]; 
       longestLength = longestString.Length; 
      } 
     } 
     cache[calcCachePos(indexes, strings)] = longestString; 
     return longestString; 
    } 
} 
int calcCachePos(int[] indexes, string[] strings) 
{ 
    int factor = 1; 
    int pos = 0; 
    for (int i = 0; i < indexes.Length; i++) 
    { 
     pos += indexes[i] * factor; 
     factor *= strings[i].Length; 
    } 
    return pos; 
} 

私のコード例はさらに最適化することができます。キャッシュされている文字列の多くは重複しており、重複している文字列が1つだけ追加されているものもあります。これは、入力文字列が大きくなるときに必要以上のスペースを使用します。入力時に

：LCSが返さ "666222054263314443712"、 "5432127413542377777"、 "6664664565464057425"

が、それは3つの文字列の代わりに、2のために働くの変更 "54442"