最长的共同连续子 [英] longest common consecutive subsequence

问题描述

我知道如何找到两个序列/字符串的LCS，但LCS不征收该子必须是连续的限制。我已经试过如下：

I know how to find the lcs of two sequences/strings, but lcs doesn't impose a restriction that the subsequence needs to be consecutive. I've tried it as follows

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：] 表示第一个切片，从第一个字符开始。

where longest_string returns the longest string in an array, and s[1:] means a slice of s, starting from the first character.

我内外在JavaScript的浏览器运行它，并在golang，在这里我把每个呼叫在自己的goroutine到低成本航空公司，但我不知道有关服务器的硬件规格在远程服务器上，所以我没有思想这些程序的并行化。

I've run this both inside a browser in javascript, and in golang, on a remote server where I put each call to lccs in its own goroutine, although I have no idea about the server's hardware specs, so I have no idea of the parallelization of these routines.

在这两种情况下，我需要的方式运行太慢。有没有一种方法，以加快这？

In both these cases, in ran way too slowly for my needs. Is there a way to speed this up?

推荐答案

我认为，基本的想法是使用动态规划。这样的事情：

I believe that the basic idea would be to use dynamic programming. something like that:

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

此问题是基本上similra到序列比对的上下文中，生物信息学中常用的。其实，你应该能够使用现有的序列比对算法为你的目的（如爆炸等），通过设置差距的处罚，以非常高的价值，几乎不允许空白对准

this question is basically similra to the context of sequence alignment, common in bioinformatics. in fact, you should be able to use existing sequence alignment algorithms for your purpose (such as blast, etc.) by setting the "gap" penalties to very high values, practically disallowing gaps in the alignment

这篇关于最长的共同连续子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！