共查询到20条相似文献,搜索用时 10 毫秒
1.
2.
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. 相似文献
3.
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. 相似文献
4.
An efficient algorithm is presented that solves a generalization of the Longest Common Subsequence problem, in which both of the input strings consists of sets of symbols which may be permuted. 相似文献
5.
An efficient algorithm is presented that solves a generalization of the Longest Common Subsequence problem, in which one of the two input strings contains sets of symbols which may be permuted. This problem arises from a music application. 相似文献
6.
7.
There are two general approaches to the longest common subsequence problem. The dynamic programming approach takes quadratic time but linear space, while the nondynamic-programming approach takes less time but more space. We propose a new implementation of the latter approach which seems to get the best for both time and space for the DNA application. 相似文献
8.
Let A=〈a1,a2,…,am〉 and B=〈b1,b2,…,bn〉 be two sequences, where each pair of elements in the sequences is comparable. A common increasing subsequence of A and B is a subsequence 〈ai1=bj1,ai2=bj2,…,ail=bjl〉, where i1<i2<?<il and j1<j2<?<jl, such that for all 1?k<l, we have aik<aik+1. A longest common increasing subsequence of A and B is a common increasing subsequence of the maximum length. This paper presents an algorithm for delivering a longest common increasing subsequence in O(mn) time and O(mn) space. 相似文献
9.
手机等移动设备的普及,使得微博等社交网络成为信息发布和共享的重要渠道。但同时,大量的反动、虚假、色情信息充斥着整个网络,谣言的恶劣影响日益突出,一些谣言的出现已经严重影响了人们对网络信息的获取和正常使用。如何对网络中的各类谣言进行检测,挖掘出谣言的源头及传播方式成为当前公安网信部门亟需解决的问题。本文以微博谣言为例,根据现有的LCS最长公共子序列算法在构造序列表格时做了相应的改进,并根据改进的LCS算法比对分析微博谣言。初步实验表明,改进后的算法可以更高效地对微博谣言进行比对溯源,从而帮助公安机关发现微博谣言源头。 相似文献
10.
郭冬梅 《计算机技术与发展》2014,(5):40-43
探讨了最长公共上升子序列(LCIS)问题,在前人算法的基础上提出一种高效求解LCIS的动态规划算法。对于LCIS问题,分别使用最长公共子序列(LCS)和最长上升子序列(LIS)相结合的算法、动态规划算法、经过状态压缩的改进动态规划算法进行设计,并对后两种算法进行了实现。设计的状态压缩的动态规划算法,实现了LCIS的快速求解。通过分析这三种算法的时间和空间复杂度,最终提出了时间复杂度为O(mn)、空间复杂度为O(m)或O(n)的基于状态压缩的快速LCIS算法。 相似文献
11.
首先重新审视了采用穷举法求解LCS问题的困难,以及对应的优点;随后针对穷举法的优点进行了两类优化;最后给出了算法实现的图示以及算法的结论。通过实验证明,算法的效率较传统的动态规划的LCS算法有了很大的提升。 相似文献
12.
13.
Bassel Mannaa 《Information Processing Letters》2010,110(21):961-721
In this paper we consider the cluster editing problem for a special type of graphs, where the vertices represent points on the real line and there is an edge between each two vertices for which the distance between their corresponding points on the line is less than a given constant. We give a polynomial time cluster editing algorithm for this class of graphs. 相似文献
14.
微博是基于关系的信息分享、传播以及获取的平台,是网络舆情发起的源头、信息传播的重要阵地。微博便捷
的转发操作,使得大量相同或相似的微博页面在微博空间内迅速传播。对微博相似页面进行检测,对于减轻用户浏览负
担和提高网络舆情分析的效率有着重要的意义。本文针对微博相似页面提出了一种基于 LCS 的微博相似页面检测方法:
首先计算可能相似的微博页面文档子集,其次计算其 LCS 并提取可信部分,最终检测出微博相似页面。实验表明,这一
方法能准确、高效地检测出微博数据中的相似页面。 相似文献
15.
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. 相似文献
16.
赵福生 《电脑与微电子技术》2011,(20):30-31,36
在字符串的运算中,求两个字符串的最长公共子串是一个重要的算法,有着广泛的应用价值。一般认为一共有两大类解法,之所以叫两大类,是因为每一类都可以再细致划分。前一类易理解,占用内存单元大,时间复杂度低,后一类复杂,最好和KMP算法结合。 相似文献
17.
在字符串的运算中,求两个字符串的最长公共子串是一个重要的算法,有着广泛的应用价值。一般认为一共有两大类解法,之所以叫两大类,是因为每一类都可以再细致划分。前一类易理解,占用内存单元大,时间复杂度低,后一类复杂,最好和KMP算法结合。 相似文献
18.
Given two strings, X and Y, both of length O(n) over alphabet
Σ, a basic problem (local alignment) is to find pairs
of similar substrings, one from X and one from Y. For
substrings X' and Y' from X and Y, respectively, the
metric we use to measure their similarity is normalized
alignment value: LCS(X',Y')/(|X'|+|Y'|). Given an integer M
we consider only those substrings whose LCS length is at least
M. We present an algorithm that reports the pairs of substrings
with the highest normalized alignment value in
O(n log|Σ|+rM log log n) time (r—the number of
matches between X and Y). We also present an
O(n log|Σ|+rL log log n) algorithm (L = LCS(X,Y)) that
reports all substring pairs with a normalized alignment value
above a given threshold. 相似文献
19.
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. 相似文献
20.
《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. 相似文献