<p>我只是为了做一个家庭作业,所以这里是我的python动态编程解决方案,非常有效。它是O(n m l),其中n,m和l是三个序列的长度。</p>
<p>该解决方案通过创建一个3D数组,然后枚举所有三个序列来计算最长子序列的路径。然后,您可以在数组中进行回溯,以从其路径重建实际的子序列。</p>
<p>因此,将数组初始化为所有零,然后枚举这三个序列。在枚举的每个步骤中,您可以在最长子序列的长度(如果存在匹配项)中添加一个子序列,或者从枚举的上一个步骤中仅结转最长子序列。</p>
<p>枚举完成后,现在可以跟踪数组,以便根据所采取的步骤重建子序列。i、 e.当你从数组中的最后一个条目向后移动时,每次遇到匹配项时,你都会在任何序列中查找它(使用数组中的坐标)并将其添加到子序列中。</p>
<pre><code>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]
</code></pre>