New algorithms for the LCS problem
The LCS problem is to determine a longest common subsequence (LCS) of two symbol sequences. Two algorithms which improve two existing results, respectively, are presented. Let m, n be the lengths of the two input strings, with \(M\leq n\), \(\rho\) being the length of the LCS, and s being the number of distinct symbols appearing in the two strings. It is shown that the first algorithm presented requires at most \(O(n \log s)\) preprocessing time and \(O(\rho m \log(n/m)+\rho m)\) processing time to solve the problem. This bound is better than that of previous algorithms especially when n is much greater than m. The algorithm also exhibits desirable properties under conditions of sparse matches. The second scheme achieves essentially the same bound \((O(\rho m \log(n/\rho)+\rho m))\) by employing efficient merging methods in the computations. It also outperforms existing algorithms designed for sparsely-matched situations. Together, the two algorithms provide interesting contrasts of different approaches to one problem; they also offer improved alternatives for actual implementation.
- A fast algorithm for computing longest common subsequences
- A fast algorithm for the longest-common-subsequence problem
- A Fast Merging Algorithm
- A faster algorithm computing string edit distances
- A linear space algorithm for computing maximal common subsequences
- A Sentence-to-Sentence Clustering Procedure for Pattern Analysis
- A Simple Algorithm for Merging Two Disjoint Linearly Ordered Sets
- Algorithms for the Longest Common Subsequence Problem
- An algorithm for the distance between two finite sequences
- An Extension of the String-to-String Correction Problem
- An information-theoretic lower bound for the longest common subsequence problem
- Bounds for the String Editing Problem
- Bounds on the Complexity of the Longest Common Subsequence Problem
- Fast Pattern Matching in Strings
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 3557227 (Why is no real title available?)
- scientific article; zbMATH DE number 3449757 (Why is no real title available?)
- scientific article; zbMATH DE number 3249566 (Why is no real title available?)
- scientific article; zbMATH DE number 3340123 (Why is no real title available?)
- Longest common subsequences of two random sequences
- Matching Sequences under Deletion/Insertion Constraints
- On computing the length of longest increasing subsequences
- On finding minimal length superstrings
- Significant Improvements to the Hwang-Lin Merging Algorithm
- Spelling correction in systems programs
- The Complexity of Some Problems on Subsequences and Supersequences
- The string merging problem
- The String-to-String Correction Problem
- The tree-to-tree editing problem
- Tree Systems for Syntactic Pattern Recognition
- Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
- The longest common subsequence problem revisited
- The set LCS problem
- A linear space algorithm for the LCS problem
- Performance analysis of some simple heuristics for computing longest common subsequences
- Deposition and extension approach to find longest common subsequence for thousands of long sequences
- A dynamic programming solution to a generalized LCS problem
- Two algorithms for LCS consecutive suffix alignment
- A multiobjective optimization algorithm for the weighted LCS
- A new practical linear space algorithm for the longest common subsequence problem
- Fast Algorithms for Computing Tree LCS
- APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ †
- scientific article; zbMATH DE number 1998339 (Why is no real title available?)
- Sparse Dynamic Programming for Longest Common Subsequence from Fragments
- On the Set LCS and Set-Set LCS Problems
- scientific article; zbMATH DE number 842125 (Why is no real title available?)
- Longest common subsequences
- Combinatorial Pattern Matching
- New refinement techniques for longest common subsequence algorithms.
- Fast algorithms for computing tree LCS
- Automatic error correction in flexion languages
This page was built for publication: New algorithms for the LCS problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1072704)
