毕业论文移动版

步骤4 计算匹配表中r = 最高层。

对于所有匹配点并发执行。

步骤4。1 。

步骤4。2 当执行。

步骤4。2。1 从匹配表中得到前置匹配点。

步骤4。2。2 

在这个算法中，一个名为匹配表的表被用于存储匹配点。在匹配表中，每一个记录以的形式存储，它分别表明了每个记录的序号，匹配点,层次，前置匹配点的序号，当前的状态。表中的每个记录都有两种状态，对于没有被搜索过的匹配点，它的状态是，被搜索过的状态为。在每一步搜索的过程中，算法并行搜索匹配点的后继匹配点，直到表中没有状态的匹配点。在从最高层开始回溯时，根据每个匹配点前置匹配点。这个回溯过程直至最开始的匹配点才结束，它的后续节点就是一个LCS。如果最后一层有多个匹配点，回溯过程可并发执行，可同时得到多个LCS。来.自^优+尔-论,文:网www.youerw.com +QQ752018766-

X，Y的LCS存储在LCS数组中。在的算法中，每个匹配点至少产生一次直接后继点，因为裁剪操作，这个操作对于每个匹配点只能执行一次。因此，假设X,Y的匹配点数量是L，那个该算法的串行执行的时间复杂度是O(L),因为匹配点表需要存储所有的匹配点，它需要O(L)的存储空间，考虑到TX，TY的空间耗损是4（n+1）和4（m+1），算法的存储空间复杂度是，在这个算法并发实现时，每个匹配点分配给一个处理机，所有匹配点处理的操作可以并发执行，因此，每一层的复杂度是O（1），FAST_LCS的并发执行的时间步骤等于匹配点的最高层次。通过定理1，知道X,Y的LCS的长度等于匹配点的最高层次。因此，FAST_LCS的并发执行时间复杂度是O(|LCS(X,Y)|)。

通过FAST_LCS寻找多个序列的LCS，的算法FAST_LCS能够很容易地扩展至处理多个序列的LCS问题。假设有n个序列，，是的长度，。找到他们的LCS，类似于两个序列的情况，多个序列的算法首先建立多个序列的后继表，把的后继表分别标记为，其中是一个大小为的二维数组，