New algorithms for the LCS problem

DOI10.1016/0022-0000(84)90025-4zbMath0587.68045OpenAlexW2070474244MaRDI QIDQ1072704

M. W. Du, W. J. Hsu

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)

Related Items (9)

Deposition and extension approach to find longest common subsequence for thousands of long sequences ⋮ A multiobjective optimization algorithm for the weighted LCS ⋮ The longest common subsequence problem revisited ⋮ Longest common subsequences ⋮ Fast Algorithms for Computing Tree LCS ⋮ Unnamed Item ⋮ Fast algorithms for computing tree LCS ⋮ Automatic error correction in flexion languages ⋮ APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ †

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On finding minimal length superstrings
• A faster algorithm computing string edit distances
• The string merging problem
• A fast algorithm for the longest-common-subsequence problem
• On computing the length of longest increasing subsequences
• An information-theoretic lower bound for the longest common subsequence problem
• The tree-to-tree editing problem
• An algorithm for the distance between two finite sequences
• Tree Systems for Syntactic Pattern Recognition
• An Extension of the String-to-String Correction Problem
• A linear space algorithm for computing maximal common subsequences
• Longest common subsequences of two random sequences
• Bounds for the String Editing Problem
• Bounds on the Complexity of the Longest Common Subsequence Problem
• A fast algorithm for computing longest common subsequences
• The Complexity of Some Problems on Subsequences and Supersequences
• Fast Pattern Matching in Strings
• A Sentence-to-Sentence Clustering Procedure for Pattern Analysis
• A Fast Merging Algorithm
• Algorithms for the Longest Common Subsequence Problem
• Significant Improvements to the Hwang-Lin Merging Algorithm
• The String-to-String Correction Problem
• Spelling correction in systems programs
• Matching Sequences under Deletion/Insertion Constraints
• A Simple Algorithm for Merging Two Disjoint Linearly Ordered Sets

This page was built for publication: New algorithms for the LCS problem