我试图找到 3 个或更多字符串的最长公共子序列。Wikipedia 文章很好地描述了如何为 2 个字符串执行此操作，但我有点不确定如何将其扩展到 3 个或更多字符串。
有很多库可以找到 2 个字符串的 LCS，所以如果可能的话，我想使用其中一个。如果我有3个字符串A，B和C，找到A和B的LCS作为X是否有效，然后找到X和C的LCS，或者这是错误的方法吗？
我在 Python 中实现了如下：
import difflib
def lcs(str1, str2):
sm = difflib.SequenceMatcher()
sm.set_seqs(str1, str2)
matching_blocks = [str1[m.a:m.a+m.size] for m in sm.get_matching_blocks()]
return "".join(matching_blocks)
print reduce(lcs, ['abacbdab', 'bdcaba', 'cbacaa'])
这输出“ba”，但它应该是“baa”。
只是概括递归关系。
对于三个字符串：
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
应该很容易从这里推广到更多的字符串。
我只需要为作业做这个，所以这是我在 python 中的动态编程解决方案，它非常有效。它是 O(nml)，其中 n、m 和 l 是三个序列的长度。
该解决方案的工作原理是创建一个 3D 数组，然后枚举所有三个序列以计算最长子序列的路径。然后，您可以通过数组回溯以从其路径重建实际的子序列。
因此，您将数组初始化为全零，然后枚举三个序列。在枚举的每一步，您要么在最长子序列的长度上加一个（如果有匹配项），要么只从枚举的上一步继承最长的子序列。
枚举完成后，您现在可以追溯数组，以根据您采取的步骤重建子序列。即，当您从数组中的最后一个条目向后移动时，每次遇到匹配项时，您都会在任何序列中查找它（使用数组中的坐标）并将其添加到子序列中。
def lcs3(a, b, c):
m = len(a)
l = len(b)
n = len(c)
subs = [[[0 for k in range(n+1)] for j in range(l+1)] for i in range(m+1)]
for i, x in enumerate(a):
for j, y in enumerate(b):
for k, z in enumerate(c):
if x == y and y == z:
subs[i+1][j+1][k+1] = subs[i][j][k] + 1
else:
subs[i+1][j+1][k+1] = max(subs[i+1][j+1][k],
subs[i][j+1][k+1],
subs[i+1][j][k+1])
# return subs[-1][-1][-1] #if you only need the length of the lcs
lcs = ""
while m > 0 and l > 0 and n > 0:
step = subs[m][l][n]
if step == subs[m-1][l][n]:
m -= 1
elif step == subs[m][l-1][n]:
l -= 1
elif step == subs[m][l][n-1]:
n -= 1
else:
lcs += str(a[m-1])
m -= 1
l -= 1
n -= 1
return lcs[::-1]
要找到 2 个字符串 A 和 B 的最长公共子序列 (LCS)，您可以对角线遍历二维数组，如您发布的链接中所示。数组中的每个元素都对应于寻找子串 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”
下面的代码可以找到 N 个字符串中最长的公共子序列。这使用 itertools 生成所需的索引组合，然后使用这些索引来查找公共子字符串。
示例执行：
输入：
输入序列数：3
输入序列 1：83217
输入序列 2：8213897
输入序列 3：683147
输出：
837
from itertools import product
import numpy as np
import pdb
def neighbors(index):
N = len(index)
for relative_index in product((0, -1), repeat=N):
if not all(i == 0 for i in relative_index):
yield tuple(i + i_rel for i, i_rel in zip(index, relative_index))
def longestCommonSubSequenceOfN(sqs):
numberOfSequences = len(sqs);
lengths = np.array([len(sequence) for sequence in sqs]);
incrLengths = lengths + 1;
lengths = tuple(lengths);
inverseDistances = np.zeros(incrLengths);
ranges = [tuple(range(1, length+1)) for length in lengths[::-1]];
for tupleIndex in product(*ranges):
tupleIndex = tupleIndex[::-1];
neighborIndexes = list(neighbors(tupleIndex));
operationsWithMisMatch = np.array([]);
for neighborIndex in neighborIndexes:
operationsWithMisMatch = np.append(operationsWithMisMatch, inverseDistances[neighborIndex]);
operationsWithMatch = np.copy(operationsWithMisMatch);
operationsWithMatch[-1] = operationsWithMatch[-1] + 1;
chars = [sqs[i][neighborIndexes[-1][i]] for i in range(numberOfSequences)];
if(all(elem == chars[0] for elem in chars)):
inverseDistances[tupleIndex] = max(operationsWithMatch);
else:
inverseDistances[tupleIndex] = max(operationsWithMisMatch);
# pdb.set_trace();
subString = "";
mainTupleIndex = lengths;
while(all(ind > 0 for ind in mainTupleIndex)):
neighborsIndexes = list(neighbors(mainTupleIndex));
anyOperation = False;
for tupleIndex in neighborsIndexes:
current = inverseDistances[mainTupleIndex];
if(current == inverseDistances[tupleIndex]):
mainTupleIndex = tupleIndex;
anyOperation = True;
break;
if(not anyOperation):
subString += str(sqs[0][mainTupleIndex[0] - 1]);
mainTupleIndex = neighborsIndexes[-1];
return subString[::-1];
numberOfSequences = int(input("Enter the number of sequences: "));
sequences = [input("Enter sequence {} : ".format(i)) for i in range(1, numberOfSequences + 1)];
print(longestCommonSubSequenceOfN(sequences));
这是解决方案视图解释的链接，这里的输出是Length of LCS is 2
# Python program to find
# LCS of three strings
# Returns length of LCS
# for X[0..m-1], Y[0..n-1]
# and Z[0..o-1]
def lcsOf3(X, Y, Z, m, n, o):
L = [[[0 for i in range(o+1)] for j in range(n+1)]
for k in range(m+1)]
''' Following steps build L[m+1][n+1][o+1] in
bottom up fashion. Note that L[i][j][k]
contains length of LCS of X[0..i-1] and
Y[0..j-1] and Z[0.....k-1] '''
for i in range(m+1):
for j in range(n+1):
for k in range(o+1):
if (i == 0 or j == 0 or k == 0):
L[i][j][k] = 0
elif (X[i-1] == Y[j-1] and
X[i-1] == Z[k-1]):
L[i][j][k] = L[i-1][j-1][k-1] + 1
else:
L[i][j][k] = max(max(L[i-1][j][k],
L[i][j-1][k]),
L[i][j][k-1])
# L[m][n][o] contains length of LCS for
# X[0..n-1] and Y[0..m-1] and Z[0..o-1]
return L[m][n][o]
# Driver program to test above function
X = 'AGGT12'
Y = '12TXAYB'
Z = '12XBA'
m = len(X)
n = len(Y)
o = len(Z)
print('Length of LCS is', lcsOf3(X, Y, Z, m, n, o))
# This code is contributed by Soumen Ghosh.