Computing a longest common subsequence for a set of strings

DOI10.1007/BF01934514zbMath0528.68049OpenAlexW2003021193MaRDI QIDQ786541

W. J. Hsu, M. W. Du

Publication date: 1984

Published in: BIT (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01934514

zbMATH Keywords

analysis of algorithmslongest common subsequence24, 45-59 (1984)string merging

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68R99)

Related Items (16)

Beam search for the longest common subsequence problem ⋮ Mathematical programming strategies for solving the minimum common string partition problem ⋮ Searching subsequences ⋮ RNA multiple structural alignment with longest common subsequences ⋮ Construct, Merge, Solve \& Adapt A new general algorithm for combinatorial optimization ⋮ A hardness result and new algorithm for the longest common palindromic subsequence problem ⋮ Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier ⋮ A hyper-heuristic for the longest common subsequence problem ⋮ On the approximation of shortest common supersequences and longest common subsequences ⋮ A large neighborhood search heuristic for the longest common subsequence problem ⋮ An improved algorithm for the longest common subsequence problem ⋮ Computational performance evaluation of two integer linear programming models for the minimum common string partition problem ⋮ Directed acyclic subsequence graph -- overview ⋮ Anytime algorithms for the longest common palindromic subsequence problem ⋮ Automatic error correction in flexion languages ⋮ Enumeration of maximal common subsequences between two strings

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
• 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
• Algorithms for the Longest Common Subsequence Problem
• The String-to-String Correction Problem
• Spelling correction in systems programs
• Matching Sequences under Deletion/Insertion Constraints

This page was built for publication: Computing a longest common subsequence for a set of strings