New algorithms for the LCS problem

DOI10.1016/0022-0000(84)90025-4MaRDI QIDQ1072704zbMATH OpenOpenAlexFDO

Authors W. J. Hsu, M. W. Du

Publication date 1984

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(84)90025-4

zbMATH Keywords

longest common subsequence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The longest common subsequence problem revisited
• Publication:4862293
• A new practical linear space algorithm for the longest common subsequence problem
• Fast linear-space computations of longest common subsequences
• A fast and practical bit-vector algorithm for the longest common subsequence problem

Cites work

• 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?)
• A Fast Merging Algorithm
• A Sentence-to-Sentence Clustering Procedure for Pattern Analysis
• A Simple Algorithm for Merging Two Disjoint Linearly Ordered Sets
• A fast algorithm for computing longest common subsequences
• A fast algorithm for the longest-common-subsequence problem
• A faster algorithm computing string edit distances
• A linear space algorithm for computing maximal common subsequences
• Algorithms for the Longest Common Subsequence Problem
• An Extension of the String-to-String Correction Problem
• An algorithm for the distance between two finite sequences
• 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
• 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-to-String Correction Problem
• The string merging problem
• The tree-to-tree editing problem
• Tree Systems for Syntactic Pattern Recognition

Cited in

(21)

• Two algorithms for LCS consecutive suffix alignment
• The longest common subsequence problem revisited
• scientific article; zbMATH DE number 1998339 (Why is no real title available?)
• A new practical linear space algorithm for the longest common subsequence problem
• scientific article; zbMATH DE number 842125 (Why is no real title available?)
• Sparse Dynamic Programming for Longest Common Subsequence from Fragments
• On the Set LCS and Set-Set LCS Problems
• A linear space algorithm for the LCS problem
• Combinatorial Pattern Matching
• APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ †
• Performance analysis of some simple heuristics for computing longest common subsequences
• A dynamic programming solution to a generalized LCS problem
• Automatic error correction in flexion languages
• Fast algorithms for computing tree LCS
• A multiobjective optimization algorithm for the weighted LCS
• The set LCS problem
• Longest common subsequences
• Fast Algorithms for Computing Tree LCS
• New refinement techniques for longest common subsequence algorithms.
• Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
• Deposition and extension approach to find longest common subsequence for thousands of long sequences

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)