3个字符串中最长的公共子序列

问题描述：

我已经实现了动态编程解决方案，以查找2个字符串中最长的公共子序列。显然有一种方法可以推广这种算法来查找3个字符串之间的LCS，但是在我的研究中，我还没有找到关于如何去做这件事的任何信息。任何帮助，将不胜感激。3个字符串中最长的公共子序列

改变它的3串，而不是2的工作是不是真正的 “泛化”。如果你在推广，那么它应该适用于任何数量的字符串。 –

啊。在这种情况下，我需要它为3个字符串工作，不一定是任何数字。 –

答

推广递归关系。

对于三个字符串：

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拍摄。

从此复制粘贴[answer]（http://stackoverflow.com/a/5057362/3375713）。至少你应该在你的回答中提到原作者的名字。 –

答

要找到2个字符串A和B的最长公共子序列（LCS），可以像对待发布的链接那样对角地遍历2维阵列。数组中的每个元素都对应于找到子串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”

3个字符串中最长的公共子序列

相关推荐