The string merging problem

DOI10.1007/BF01934067zbMath0464.68071MaRDI QIDQ1154285

Stephen Y. Itoga

Publication date: 1981

Published in: BIT (Search for Journal in Brave)

zbMATH Keywords

string matchinglongest common subsequenceshortest common supersequence21, 20-30 (1981)costs of editingstring modification

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68R99)

Related Items

Searching subsequences ⋮ Longest common subsequence problem for unoriented and cyclic strings ⋮ A hardness result and new algorithm for the longest common palindromic subsequence problem ⋮ Exact algorithms for the repetition-bounded longest common subsequence problem ⋮ A large neighborhood search heuristic for the longest common subsequence problem ⋮ Finite automata based algorithms on subsequences and supersequences of degenerate strings ⋮ Computing a longest common subsequence for a set of strings ⋮ APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ † ⋮ New algorithms for the LCS problem

Cites Work

• Unnamed Item
• An algorithm for the distance between two finite sequences
• An Extension of the String-to-String Correction Problem
• A linear space algorithm for computing maximal common subsequences
• Bounds for the String Editing Problem
• Optimal Code Generation for Expression Trees
• A fast algorithm for computing longest common subsequences
• The Complexity of Some Problems on Subsequences and Supersequences
• The String-to-String Correction Problem
• Studies in abstract families of languages
• Matching Sequences under Deletion/Insertion Constraints