algorithm - 最长的公共(public)连续子序列

我知道如何找到两个序列/字符串的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)

其中longest_string返回数组中最长的字符串，s[1:]表示从第一个字符开始的s片。
我在javascript浏览器和golang远程服务器上都运行过这个程序，在这个服务器上，我把对lcc的每个调用都放在自己的goroutine中，尽管我不知道服务器的硬件规格，所以我不知道这些例程的并行化。
在这两种情况下，跑步的速度都太慢了。有办法加快速度吗？

最佳答案

我相信基本的想法是使用动态编程像这样的：

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
        }
    }
}

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

关于algorithm - 最长的公共(public)连续子序列，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22158130/