求最长公共子串的两类解法比较

在字符串的运算中,求两个字符串的最长公共子串是一个重要的算法,有着广泛的应用价值。一般认为一共有两大类解法,之所以叫两大类,是因为每一类都可以再细致划分。前一类易理解,占用内存单元大,时间复杂度低,后一类复杂,最好和KMP算法结合。     

求最长公共子串的两类解法比较

在字符串的运算中,求两个字符串的最长公共子串是一个重要的算法,有着广泛的应用价值。一般认为一共有两大类解法,之所以叫两大类,是因为每一类都可以再细致划分。前一类易理解,占用内存单元大,时间复杂度低,后一类复杂,最好和KMP算法结合。     

3字符最长公共弱递增子串的O（nloglogn）算法

最长公共子串(LCS)和最长递增子串(LIS)是两个非常经典的基础算法问题,并且在生物信息学中已有重要应用.2006年,Brodal等人提出了最长公共弱递增字串问题(LCWIS),并且给出了2字符字母表上线性时间算法和3字符字母表上O(nlogn)时间的算法.本文中,我们提出了一种新的在3字符字母表上寻找最长公共弱递增子串(LC-WIS)的算法.该算法利用了两个成熟的数据结构:约束堆(Bounded heap)和van Emde Boas树.我们算法的时间复杂度是O(nloglogn),空间复杂度为0(n),两者都是目前为止最优的.     

两种基于双向比较的最长公共子串算法

查找两个给定字符串的最长公共子串(LCSstr)是一类重要字符串分析问题,在字符串近似匹配、计算机病毒特征码对比等方面有着广泛的用途.最长公共子串算法目前主要包括动态规划算法(LCSstrDP)和后缀数组算法(LCSstrSA),分别用于短串和长串的最长公共子串计算.前者代码简洁,但计算速度较慢,后者速度很快但算法非常复杂.提出两种基于双向比较的最长公共子串算法,即LCSstrSeL和LCSstrSCeL.LCSstrSeL跨越已有的最长公共子串长度,与LCSstrDP相比,代码同样简洁,平均计算效率提高近一个数量级,并且不需要额外的存储空间.LCSstrSCeL是在LCSstrSeL的基础上,增加字符跨越、连续同值区间跨越等机制,平均效率较LCSstrSeL亦有一定程度的提高,内存开销与LCSstrDP相近,在中小长度的字符串LCSstr计算中,平均计算效率高于LCSstrSA,某些情况下的计算效率可达到亚线性的速度.     

基于最长公共子串挖掘的未知链路层协议帧切割算法

在日益激烈的现代电子对抗领域中,侦听方截获的原始数据一般是比特流的形式,将比特流划分为数据帧是处理截获数据的首要任务。现有方法虽然可以准确地提取相关序列实现帧切分,但是当需要处理的数据量较大时,时间和空间的消耗量过大,并且实验过程中常常需要预先设定一些阈值。为此,文中提出了一种基于最长公共子串挖掘的未知链路层协议帧切割算法,该算法通过统计一定长度的比特流的最长公共子串,逐步精确前导码和帧起始定界符,从而实现帧切分。实验数据表明,该算法相较于基于频繁序列挖掘以实现帧切分的算法,相关候选序列数量呈指数级下降,最终使得候选序列唯一。该算法的时间复杂度为O(n),且只需单次扫描,充分说明该算法可以高效地实现帧切分。     

最长公共子序列的快速算法及其并行实现

求生物序列的最长公共子串是生物信息学中最重要的问题之一,提出了该问题的一个快速算法,可对所有初始同字符对并行地寻找其后继同字符对,并记录下相应层次值。最后通过最大层次值回溯得到比对结果。此外,该算法采用了剪枝技术,对于明显不能得出最优比对的同字符将中止其后继的搜索。实验结果证明,本文算法比其他算法速度快、精确度高。     

基于状态压缩的最长公共上升子序列快速算法

探讨了最长公共上升子序列（LCIS）问题,在前人算法的基础上提出一种高效求解LCIS的动态规划算法。对于LCIS问题,分别使用最长公共子序列（LCS）和最长上升子序列（LIS）相结合的算法、动态规划算法、经过状态压缩的改进动态规划算法进行设计,并对后两种算法进行了实现。设计的状态压缩的动态规划算法,实现了LCIS的快速求解。通过分析这三种算法的时间和空间复杂度,最终提出了时间复杂度为O（mn）、空间复杂度为O（m）或O（n）的基于状态压缩的快速LCIS算法。     

求解最长循环公共子序列问题的两个算法

最长循环公共子序列（LCCS）是两个字符串在所有可能的循环移位操作下能得到的最长公共子序列（LCS）。针对穷举移位量求解LCCS效率过低的问题,设法对候选移位量进行筛选。通过证明循环移位操作对两字符串间LCS长度增量影响的上下限,得到最优移位量的必要条件,从而减小了求解LCCS的枚举量;在此基础上,建立了求解LCCS的迭代方法,只经过少数几次迭代便可消除绝大部分无效候选移位量;此外,还提出一个可在◢O（mn）◣时间复杂度下快速估算LCCS长度的近似算法。大量随机模拟表明,当两字符串间的相似度明显高于随机字符串的相似度时,提出的两种算法表现良好。     

最长公共子序列问题的改进快速算法

现在几个最常用的解决最长公共子序列(LCS)问题的算法的时间复杂度分别是O(pn),O(n(m-p)).这里m、n为两个待比较字符串的长度,p是最长公共子串的长度.给出一种时间复杂度为O(p(m-p)),空间复杂度为O(m+n)的算法.与以前的算法相比,不管在p<相似文献   

一种高效的广义后缀数组构造算法

本文介绍了后缀数组和广义后缀数组的概念,然后提出了一种类似桶排序的广义后缀数组的高效构造算法,并对算法的复杂度进行了分析.     

An Efficient Systolic Algorithm for the Longest Common Subsequence Problem

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.     

A New Efficient Algorithm for Computing the Longest Common Subsequence

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.     

A fast and practical bit-vector algorithm for the Longest Common Subsequence problem

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.     

Computing Longest Previous Factor in linear time and applications

We give two optimal linear-time algorithms for computing the Longest Previous Factor (LPF) array corresponding to a string w. For any position i in w, LPF[i] gives the length of the longest factor of w starting at position i that occurs previously in w. Several properties and applications of LPF are investigated. They include computing the Lempel-Ziv factorization of a string and detecting all repetitions (runs) in a string in linear time independently of the integer alphabet size.     

Finding the longest common nonsuperstring in linear time

String inclusion and non-inclusion problems have been vigorously studied in such diverse fields as molecular biology, data compression, and computer security. Among the well-known string inclusion or non-inclusion notions, we are interested in the longest common nonsuperstring. Given a set of strings, the longest common nonsuperstring problem is finding the longest string that is not a superstring of any string in the given set. It is known that the longest common nonsuperstring problem is solvable in polynomial time.In this paper, we propose an efficient algorithm for the longest common nonsuperstring problem. The running time of our algorithm is linear with respect to the sum of the lengths of the strings in the given set, using generalized suffix trees.     

Matching statistics: efficient computation and a new practical algorithm for the multiple common substring problem

We present new algorithms for computing matching statistics with suffix arrays. We show how the Multiple Common Substring Problem can be solved efficiently in practice with a new approach using matching statistics. This problem consists of finding the common substrings of a set of strings. For the computation of matching statistics we compare seven different methods based on suffix trees and suffix arrays. Most of the suffix array algorithms have an inferior asymptotic worst case running time but a very low memory overhead and small constants in the running time complexity. Our experiments show a good performance in practice. Copyright © 2005 John Wiley & Sons, Ltd.     

基于格代数的最长公共子序列近似求解

多条序列的最长公共子序列可以代表多条序列的公共信息,其在诸多领域里有着重要的应用,如信息检索、基因序列匹配等。求解多条序列的最长公共子序列是著名的NP难问题,本质为多解问题。一些近似算法虽然时间复杂度较低,但只能求出单解,对于有多解的序列集合,求得的结果信息量损失较大。因此提出一个新的近似算法来解决最长公共子序列问题。算法引入了代数结构“格”,通过动态规划求解出两条序列的公共格,并递归求解当前格与当前序列的公共格。公共格中的路径保存了多条公共子序列使得最终求解出的最长公共子序列为多个。对算法的相关定理给出了理论证明,并通过实验验证了算法的正确性。