0

我知道如何找到两个序列/字符串的 lcs，但 lcs 并没有限制子序列必须是连续的。我已经尝试如下

function lccs(a, b)
    if a.length == 0 or b.length == 0
        return ""
    possible = []
    if a[0] == b[0]
      possible.push(lcs(a[1:), b[1:])
    possible.push(lcs(a[1:], b))
    possible.push(lcs(a, b[1:))
    return longest_string(possible)

wherelongest_string返回数组中最长的字符串，s[1:]表示从第一个字符开始的 s 切片。

我已经在 javascript 中的浏览器和 golang 中运行它，在远程服务器上，我将每个对 lccs 的调用放在它自己的 goroutine 中，虽然我不知道服务器的硬件规格，所以我不知道这些例程的并行化。

在这两种情况下，对于我的需求来说，运行速度都太慢了。有没有办法加快这个速度？

4

1 回答 1

1

我相信基本思想是使用动态编程。类似的东西：

for i in 1:length(a) {
    for j in 1:length(b) {
        if (a[i]==b[j]) then {
            result[i,j] = result[i-1,j-1]+1 #remember to initialize the borders with zeros
            # track the maximum of the matrix
        } else {
            result[i,j]=0
        }
    }
}

这个问题基本上类似于生物信息学中常见的序列比对的上下文。事实上，您应该能够将现有的序列比对算法用于您的目的（例如爆炸等），方法是将“间隙”惩罚设置为非常高的值，实际上不允许比对中的间隙

于 2014-03-03T22:32:03.113 回答