An efficient algorithm for LCS problem between two arbitrary sequences

DOI10.1155/2018/4158071MaRDI QIDQ1720875zbMATH OpenOpenAlexFDO

Authors Yubo Li

Publication date 8 February 2019

Published in Mathematical Problems in Engineering (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1155/2018/4158071

Mathematics Subject Classification ID

Algorithms on strings (68W32) Analysis of algorithms (68W40)

Review text

Summary: The longest common subsequence (LCS) problem is a classic computer science problem. For the essential problem of computing LCS between two arbitrary sequences \(s 1\) and \(s 2\), this paper proposes an algorithm taking \(O(n + r)\) space and \(O(r + n^2)\) time, where \(r\) is the total number of elements in the set \(\left\{(i, j) \mid s 1 [i] = s 2 [j]\right\}\). The algorithm can be more efficient than relevant classical algorithms in specific ranges of \(r\).

Recommendations

• A new efficient algorithm for computing the longest common subsequence
• A New Efficient Algorithm for Computing the Longest Common Subsequence
• A new practical linear space algorithm for the longest common subsequence problem
• Publication:4862293
• A linear space algorithm for the LCS problem

Cites work

• A bit-string longest-common-subsequence algorithm
• A fast algorithm for computing longest common subsequences
• A fast and practical bit-vector algorithm for the longest common subsequence problem
• A faster algorithm computing string edit distances
• A linear space algorithm for computing maximal common subsequences
• A longest common subsequence algorithm suitable for similar text strings
• Algorithms for the Longest Common Subsequence Problem
• Algorithms on Strings, Trees and Sequences
• Bounds on the Complexity of the Longest Common Subsequence Problem
• Fast and compact regular expression matching
• scientific article; zbMATH DE number 3340123 (Why is no real title available?)
• Longest common subsequences of two random sequences
• New tabulation and sparse dynamic programming based techniques for sequence similarity problems
• Sparse dynamic programming I
• The central limit theorem around 1935. With comments, and a rejoinder by the author
• The Complexity of Some Problems on Subsequences and Supersequences
• The early history of the factorial function
• The longest common subsequence problem revisited

Cited in

(4)

• A linear space algorithm for the LCS problem
• Extension of van der Corput algorithm to LS-sequences
• String Processing and Information Retrieval
• A new efficient algorithm for computing the longest common subsequence

This page was built for publication: An efficient algorithm for LCS problem between two arbitrary sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1720875)