我正在尝试寻找3个或更多字符串的最长公共子序列。维基百科文章有一个很好的描述，介绍了如何为两个字符串解决此问题，但我不太确定如何将其扩展到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是三个序列的长度。
这个解决方案的工作原理是创建一个三维数组，然后枚举所有三个序列来计算最长子序列的路径。然后你可以通过回溯数组来从其路径重构实际子序列。
因此，你需要将数组初始化为所有零，然后枚举三个序列。在枚举的每一步中，如果有匹配项，则将最长子序列的长度加1，否则就从枚举的前一步中继续最长子序列。
完成枚举后，现在可以通过遍历数组来从你所采取的步骤中重构子序列。从数组中的最后一个条目向后移动时，每次遇到匹配项都会在任何序列中查找它（使用数组的坐标），并将其添加到子序列中。
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]
以下代码可以在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));
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;
}
这里是解决方案的链接查看此处的解释输出是LCS的长度为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.
abc12、12abc、12xyz错误的结果。 - sth('abacbdab', 'bdcaba')，至少存在五个最长公共子序列："baa", "bab", "bca", "bcb", "dab"。您的代码是否考虑到了这一点？ - ypercubeᵀᴹ