共查询到20条相似文献,搜索用时 0 毫秒
1.
最长公共子序列问题的改进快速算法 总被引:1,自引:0,他引:1
现在几个最常用的解决最长公共子序列(LCS)问题的算法的时间复杂度分别是O(pn),O(n(m-p)).这里m、n为两个待比较字符串的长度,p是最长公共子串的长度.给出一种时间复杂度为O(p(m-p)),空间复杂度为O(m+n)的算法.与以前的算法相比,不管在p<相似文献
2.
In the longest common subsequence problem the task is to find the longest sequence of letters that can be found as a subsequence
in all members of a given finite set of sequences. The problem is one of the fundamental problems in computer science with
the task of finding a given pattern in a text as an important special case. It has applications in bioinformatics; problem-specific
algorithms and facts about its complexity are known. Motivated by reports about good performance of evolutionary algorithms
for some instances of this problem a theoretical analysis of a generic evolutionary algorithm is performed. The general algorithmic
framework encompasses EAs as different as steady state GAs with uniform crossover and randomized hill-climbers. For all these
algorithms it is proved that even rather simple special cases of the longest common subsequence problem can neither be solved
to optimality nor approximately be solved up to an approximation factor arbitrarily close to 2. 相似文献
3.
A longest common subsequence (LCS) of two strings is a common subsequence of two strings of maximal length. The LCS problem is to find an LCS of two given strings and the length of the LCS (LLCS). In this paper, we present a new linear processor array for solving the LCS problem. The array is based on parallelization of a recent LCS algorithm which consists of two phases, i.e. preprocessing and computation. The computation phase is based on bit-level dynamic programming approach. Implementations of the preprocessing and computation phases are discussed on the same processor array architecture for the LCS problem. Further, we propose a block processor array architecture which reduces the overall communication and time requirements. Finally, we develop a performance model for estimating the performance of the processor array architecture on Pentium processors. 相似文献
4.
A longest common subsequence (LCS) of two strings is a common subsequence of the two strings of maximal length. The LCS problem is to find an LCS of two given strings and the length of the LCS (LLCS). In this paper, a fast linear systolic algorithm that improves on previous systolic algorithms for solving the LCS problem is presented. For two given strings of length m and n, where m n, the LLCS and an LCS can be found in m + 2n – 1 time steps. This algorithm achieves the tight lower bound of the time complexity under the situation where symbols are input sequentially to a linear array of n processors. The systolic algorithm can be modified to take only m + n steps on multicomputers by using the scatter operation. 相似文献
5.
Given two strings A and B of lengths na and nb, respectively, the All-substrings Longest Common Subsequence (ALCS) problem obtains, for any substring B' of B, the length
of the longest string that is a subsequence of both A and B'. The sequential algorithm for this problem takes O(na nb) time and O(nb) space. We present a
parallel algorithm for the ALCS problem on the Coarse-Grained Multicomputer (BSP/CGM) model with p < √na processors, that takes O(na nb/p) time, O(log p) communication rounds and O(nb √na) space per processor. The proposed algorithm also solves the basic Longest Common Subsequence (LCS) problem that finds the
longest string (and not only its length) that is a subsequence of both A and B. To our knowledge, this is the best BSP/CGM
algorithm in the literature for the LCS and ALCS problems. 相似文献
6.
7.
最长模式子序列问题在生物信息学中有重要的应用.本文首次提出求a=aoa1…an-1∈ωn的最长σ模式子序列的O(n2)时间算法,并对|σ|≤2的情形推广了RSK算法和标准Young表,对算法作了改进,得到了当|σ|=1时的O(nlogk)时间算法和当|σ|=2时的O(n)时间算法. 相似文献
8.
The Longest Common Subsequence (LCS) problem is a classic and well-studied problem in computer science. The LCS problem is a common task in DNA sequence
analysis with many applications to genetics and molecular biology. In this paper, we present a new and efficient algorithm
for solving the LCS problem for two strings. Our algorithm runs in O(ℛlog log n+n) time, where ℛ is the total number of ordered pairs of positions at which the two strings match.
Preliminary version appeared in [24].
C.S. Iliopoulos is supported by EPSRC and Royal Society grants.
M.S. Rahman is supported by the Commonwealth Scholarship Commission in the UK under the Commonwealth Scholarship and Fellowship
Plan (CSFP) and is on Leave from Department of CSE, BUET, Dhaka-1000, Bangladesh. 相似文献
9.
郭冬梅 《计算机技术与发展》2014,(5):40-43
探讨了最长公共上升子序列(LCIS)问题,在前人算法的基础上提出一种高效求解LCIS的动态规划算法。对于LCIS问题,分别使用最长公共子序列(LCS)和最长上升子序列(LIS)相结合的算法、动态规划算法、经过状态压缩的改进动态规划算法进行设计,并对后两种算法进行了实现。设计的状态压缩的动态规划算法,实现了LCIS的快速求解。通过分析这三种算法的时间和空间复杂度,最终提出了时间复杂度为O(mn)、空间复杂度为O(m)或O(n)的基于状态压缩的快速LCIS算法。 相似文献
10.
《Journal of Parallel and Distributed Computing》1999,57(2):212-223
Recently Aklet al. introduced a new model of parallel computation, called broadcasting with selective reduction (BSR), and showed that it is more powerful than any CRCW PRAM and yet requires no more resources for implementation than even EREW PRAM. The model allows constant time solutions to sorting, parallel prefix, and other problems. In this paper, we describe constant time solutions to the longest common subsequence problem and the sequence alignment problem using the BSR model. These are the first constant time solutions to these problems for any model of computation. 相似文献
11.
12.
Maxime Crochemore Costas S. Iliopoulos Yoan J. Pinzon James F. Reid 《Information Processing Letters》2001,80(6):279-285
This paper presents a new practical bit-vector algorithm for solving the well-known Longest Common Subsequence (LCS) problem. Given two strings of length m and n, nm, we present an algorithm which determines the length p of an LCS in O(nm/w) time and O(m/w) space, where w is the number of bits in a machine word. This algorithm can be thought of as column-wise “parallelization” of the classical dynamic programming approach. Our algorithm is very efficient in practice, where computing the length of an LCS of two strings can be done in linear time and constant (additional/working) space by assuming that mw. 相似文献
13.
手机等移动设备的普及,使得微博等社交网络成为信息发布和共享的重要渠道。但同时,大量的反动、虚假、色情信息充斥着整个网络,谣言的恶劣影响日益突出,一些谣言的出现已经严重影响了人们对网络信息的获取和正常使用。如何对网络中的各类谣言进行检测,挖掘出谣言的源头及传播方式成为当前公安网信部门亟需解决的问题。本文以微博谣言为例,根据现有的LCS最长公共子序列算法在构造序列表格时做了相应的改进,并根据改进的LCS算法比对分析微博谣言。初步实验表明,改进后的算法可以更高效地对微博谣言进行比对溯源,从而帮助公安机关发现微博谣言源头。 相似文献
14.
15.
IEC61850通信已经在电力系统中广泛使用,其中变电站通信系统使用SCD文件进行描述.SCD文件是XML格式的层次化结构,不适合直接用文本按行对比来分析差异.同时由于SCD文件层次结构多,使用纯结构化的比较方法,会导致比较结果冗长,执行效率低.本文基于SCD文件的特征,提出了分层匹配的半结构化半文本比较思路.先按照智能电子设备、连接接入点、逻辑设备等层次结构,提取关键属性名,进行对齐匹配.之后在逻辑设备范围内,针对逻辑节点的内容,采用最长公共子序列的匹配算法对比局部文本内容,该算法可去除仅调整顺序不影响实体内容的无效差异,比较速度快,比较结果准确直观. 相似文献
16.
Kiyomi Masashi Ono Hirotaka Otachi Yota Schweitzer Pascal Tarui Jun 《Theory of Computing Systems》2020,64(3):522-541
Theory of Computing Systems - Given a sequence of integers, we want to find a longest increasing subsequence of the sequence. It is known that this problem can be solved in $Oleft (n log nright... 相似文献
17.
18.
多条序列的最长公共子序列可以代表多条序列的公共信息,其在诸多领域里有着重要的应用,如信息检索、基因序列匹配等。求解多条序列的最长公共子序列是著名的NP难问题,本质为多解问题。一些近似算法虽然时间复杂度较低,但只能求出单解,对于有多解的序列集合,求得的结果信息量损失较大。因此提出一个新的近似算法来解决最长公共子序列问题。算法引入了代数结构“格”,通过动态规划求解出两条序列的公共格,并递归求解当前格与当前序列的公共格。公共格中的路径保存了多条公共子序列使得最终求解出的最长公共子序列为多个。对算法的相关定理给出了理论证明,并通过实验验证了算法的正确性。 相似文献
19.
R. A. Baeza-Yates R. Gavaldà G. Navarro R. Scheihing 《Theory of Computing Systems》1999,32(4):435-452
We present improvements to two techniques to find lower and upper bounds for the expected length of longest common subsequences
and forests of two random sequences of the same length, over a fixed size, uniformly distributed alphabet. We emphasize the
power of the methods used, which are Markov chains and Kolmogorov complexity. As a corollary, we obtain some new lower and
upper bounds for the problems addressed as well as some new exact results for short sequences.
Received November 1996, and in final form October 1998. 相似文献