An \(O(ND)\) difference algorithm and its variations
From MaRDI portal
Publication:1099955
DOI10.1007/BF01840446zbMath0639.68054WikidataQ29028524 ScholiaQ29028524MaRDI QIDQ1099955
Publication date: 1986
Published in: Algorithmica (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)
Related Items (50)
Performance analysis of some simple heuristics for computing longest common subsequences ⋮ A sublinear algorithm for approximate keyword searching ⋮ Longest common extensions in trees ⋮ Time-Space Trade-Offs for Longest Common Extensions ⋮ Fast approximate matching of words against a dictionary ⋮ Classes of cost functions for string edit distance ⋮ Computing longest common extensions in partial words ⋮ Calculating distances for dissimilar strings: the shortest path formulation revisited ⋮ Longest common subsequence problem for unoriented and cyclic strings ⋮ Longest Common Extensions in Sublinear Space ⋮ Longest common extension ⋮ On locally optimal alignments in genetic sequences ⋮ Fast Algorithms for Local Similarity Queries in Two Sequences ⋮ The longest common extension problem revisited and applications to approximate string searching ⋮ Efficient merged longest common subsequence algorithms for similar sequences ⋮ A Probabilistic Analysis of a String Editing Problem and its Variations ⋮ A Linear-Time n 0.4 -Approximation for Longest Common Subsequence ⋮ On the Longest Common Parameterized Subsequence ⋮ Relational program reasoning using compiler IR ⋮ Personalized multi-user view and content synchronization and retrieval in real-time mobile social software applications ⋮ An O(NP) sequence comparison algorithm ⋮ Time-space trade-offs for longest common extensions ⋮ An overview on XML similarity: background, current trends and future directions ⋮ EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS ⋮ DICTIONARY LOOK-UP WITHIN SMALL EDIT DISTANCE ⋮ Algorithms for computing variants of the longest common subsequence problem ⋮ A space efficient algorithm for finding the best nonoverlapping alignment score ⋮ Fast linear-space computations of longest common subsequences ⋮ An algorithm for matching run-length coded strings ⋮ Approximate string matching with suffix automata ⋮ New efficient algorithms for the LCS and constrained LCS problems ⋮ Faster approximate string matching for short patterns ⋮ Tandem cyclic alignment ⋮ Unnamed Item ⋮ Tight conditional lower bounds for longest common increasing subsequence ⋮ Unnamed Item ⋮ LightCore: Lightweight Collaborative Editing Cloud Services for Sensitive Data ⋮ A new efficient algorithm for computing the longest common subsequence ⋮ A Formal Investigation of Diff3 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A learning algorithm for the longest common subsequence problem ⋮ The set-set LCS problem ⋮ Unnamed Item ⋮ On the longest common parameterized subsequence ⋮ What’s Behind Blast ⋮ Efficient algorithms for approximate string matching with swaps ⋮ Simple and fast linear space computation of longest common subsequences ⋮ Fast and practical approximate string matching ⋮ Finding approximate palindromes in strings
Cites Work
- Unnamed Item
- A note on two problems in connexion with graphs
- A faster algorithm computing string edit distances
- A longest common subsequence algorithm suitable for similar text strings
- An information-theoretic lower bound for the longest common subsequence problem
- Fast Algorithms for Finding Nearest Common Ancestors
- A linear space algorithm for computing maximal common subsequences
- Bounds on the Complexity of the Longest Common Subsequence Problem
- A Space-Economical Suffix Tree Construction Algorithm
- A fast algorithm for computing longest common subsequences
- Algorithms for the Longest Common Subsequence Problem
- The String-to-String Correction Problem
This page was built for publication: An \(O(ND)\) difference algorithm and its variations
