一系列字符串的最長公共子序列

Question

對於2字符串的Longest Common Subsequence，我在網上找到了很多示例，我相信我理解這個解決方案。
我不明白的是，N字符串應用此問題的正確方法是什麼？以某種方式應用相同的解決方案？怎麼樣？解決方案不同嗎？什麼？

Answer 1

當輸入具有任意數量的字符串時，此問題將變爲NP-hard。當輸入具有固定數量的字符串時，此問題變得易於處理只有。如果輸入具有k個字符串，我們可以通過使用k維陣列來應用相同的DP技術來存儲子問題的最優解。

參考：Longest common subsequence problem

Answer 2

找出2串A的最長公共子序列（LCS）和B，可以遍歷一個2維陣列對角像顯示在Link你張貼。數組中的每個元素都對應於找到子串A'和B'的LCS（A被其行號切割，B被其列號切割）的問題。這個問題可以通過計算數組中所有元素的值來解決。 您必須確定在計算數組元素的值時，計算給定值所需的所有子問題已經解決。這就是爲什麼你對角地穿過二維陣列的原因。

該解決方案可以縮放到找到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; 
} 

我的代碼示例可以進一步優化。許多被緩存的字符串都是重複的，有些是重複的，只增加了一個額外的字符。當輸入字符串變大時，這會佔用更多的空間。

對於輸入："666222054263314443712", "5432127413542377777", "6664664565464057425"

的LCS返回是"54442"