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)
68Q25: Analysis of algorithms and problem complexity
68R99: Discrete mathematics in relation to computer science
Related Items
A Probabilistic Analysis of a String Editing Problem and its Variations, A Formal Investigation of Diff3, A learning algorithm for the longest common subsequence problem, EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS, DICTIONARY LOOK-UP WITHIN SMALL EDIT DISTANCE, Longest common extensions in trees, Personalized multi-user view and content synchronization and retrieval in real-time mobile social software applications, An overview on XML similarity: background, current trends and future directions, The longest common extension problem revisited and applications to approximate string searching, A space efficient algorithm for finding the best nonoverlapping alignment score, An algorithm for matching run-length coded strings, Approximate string matching with suffix automata, Faster approximate string matching for short patterns, A new efficient algorithm for computing the longest common subsequence, Calculating distances for dissimilar strings: the shortest path formulation revisited, Longest common subsequence problem for unoriented and cyclic strings, An O(NP) sequence comparison algorithm, Algorithms for computing variants of the longest common subsequence problem, New efficient algorithms for the LCS and constrained LCS problems, On the longest common parameterized subsequence, Fast linear-space computations of longest common subsequences, Efficient algorithms for approximate string matching with swaps, Performance analysis of some simple heuristics for computing longest common subsequences, A sublinear algorithm for approximate keyword searching, Classes of cost functions for string edit distance, Simple and fast linear space computation of longest common subsequences, Tandem cyclic alignment, The set-set LCS problem, Fast and practical approximate string matching, Finding approximate palindromes in strings, Fast approximate matching of words against a dictionary, Time-space trade-offs for longest common extensions, LightCore: Lightweight Collaborative Editing Cloud Services for Sensitive Data, Time-Space Trade-Offs for Longest Common Extensions, Longest Common Extensions in Sublinear Space, Fast Algorithms for Local Similarity Queries in Two Sequences, Unnamed Item, On the Longest Common Parameterized Subsequence
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
