A faster algorithm computing string edit distances
From MaRDI portal
Publication:1140994
DOI10.1016/0022-0000(80)90002-1zbMath0436.68044WikidataQ55891303 ScholiaQ55891303MaRDI QIDQ1140994
Michael S. Paterson, William J. Masek
Publication date: 1980
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(80)90002-1
68Q25: Analysis of algorithms and problem complexity
68R99: Discrete mathematics in relation to computer science
Related Items
On-Line Approximate String Searching Algorithms: Survey and Experimental Results, Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity, Normalization of edit sequences for text synchronization, A learning algorithm for the longest common subsequence problem, ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS, Quadratic-time algorithm for a string constrained LCS problem, Fast searching in packed strings, Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics, The intractability of computing the Hamming distance, Faster algorithms for computing longest common increasing subsequences, An improved algorithm for computing the edit distance of run-length coded strings, An algorithm for matching run-length coded strings, Faster approximate string matching for short patterns, LCS approximation via embedding into locally non-repetitive strings, Fast algorithms for computing tree LCS, A new efficient algorithm for computing the longest common subsequence, An algorithm for distinguishing efficiently bit-strings by their subsequences, Computing a longest common subsequence for a set of strings, A fast algorithm for computing a longest common increasing subsequence, Faster subsequence recognition in compressed strings, A linear space algorithm for computing a longest common increasing subsequence, A novel look-ahead optimization strategy for trie-based approximate string matching, Longest common subsequence problem for unoriented and cyclic strings, String matching with weighted errors, An O(NP) sequence comparison algorithm, Algorithms for computing variants of the longest common subsequence problem, Finding the longest common subsequence for multiple biological sequences by ant colony optimization, New efficient algorithms for the LCS and constrained LCS problems, Finding common structured patterns in linear graphs, Efficient algorithms for finding a longest common increasing subsequence, Semi-local longest common subsequences in subquadratic time, Shift-or string matching with super-alphabets, The constrained longest common subsequence problem, On the longest common parameterized subsequence, New algorithms for the LCS problem, Rational equivalence relations, The longest common subsequence problem revisited, Constrained string editing, An \(O(ND)\) difference algorithm and its variations, The set LCS problem, A new distance metric on strings computable in linear time, Data structures and algorithms for approximate string matching, A lower bound for the edit-distance problem under an arbitrary cost function, Fast linear-space computations of longest common subsequences, Matching for run-length encoded strings, Performance analysis of some simple heuristics for computing longest common subsequences, A fast and practical bit-vector algorithm for the longest common subsequence problem, The set-set LCS problem, Efficient error-correcting parsing for (attributed and stochastic) tree grammars, Complexity measures of words based on string matching and edit distance, Fast approximate matching of words against a dictionary, A subquadratic algorithm for approximate limited expression matching, Approximate Boyer-Moore string matching for small alphabets, Fast computation of a longest increasing subsequence and application, Fast and compact regular expression matching, Breadth-first search strategies for trie-based syntactic pattern recognition, A simple algorithm for the constrained sequence problems, Edit distance with move operations, Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition, Unnamed Item, BIT-PARALLEL COMPUTATION OF LOCAL SIMILARITY SCORE MATRICES WITH UNITARY WEIGHTS, Fast Algorithms for Computing Tree LCS, Constrained LCS: Hardness and Approximation, On the Longest Common Parameterized Subsequence, Communication-Efficient Private Protocols for Longest Common Subsequence, LCS Approximation via Embedding into Local Non-repetitive Strings, Fast Searching in Packed Strings, Periodic String Comparison, Calcul de la distance par les sous-mots, A common basis for similarity measures involving two strings†, APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ †
Cites Work
