A faster algorithm computing string edit distances
From MaRDI portal
Publication:1140994
DOI10.1016/0022-0000(80)90002-1zbMath0436.68044OpenAlexW2012010763WikidataQ55891303 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
Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)
Related Items (only showing first 100 items - show all)
Deposition and extension approach to find longest common subsequence for thousands of long sequences ⋮ Performance analysis of some simple heuristics for computing longest common subsequences ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ A faster linear systolic algorithm for recovering a longest common subsequence ⋮ A fast algorithm for computing a longest common increasing subsequence ⋮ Rational equivalence relations ⋮ Dynamic Set Intersection ⋮ Faster subsequence recognition in compressed strings ⋮ Fast and compact regular expression matching ⋮ A linear space algorithm for computing a longest common increasing subsequence ⋮ New tabulation and sparse dynamic programming based techniques for sequence similarity problems ⋮ Fast approximate matching of words against a dictionary ⋮ The longest common subsequence problem revisited ⋮ Constrained string editing ⋮ An \(O(ND)\) difference algorithm and its variations ⋮ The set LCS problem ⋮ Breadth-first search strategies for trie-based syntactic pattern recognition ⋮ A novel look-ahead optimization strategy for trie-based approximate string matching ⋮ A new distance metric on strings computable in linear time ⋮ Constrained pairwise and center-star sequences alignment problems ⋮ Data structures and algorithms for approximate string matching ⋮ A lower bound for the edit-distance problem under an arbitrary cost function ⋮ A simple algorithm for the constrained sequence problems ⋮ A subquadratic algorithm for approximate limited expression matching ⋮ Approximating the geometric edit distance ⋮ Longest common subsequence problem for unoriented and cyclic strings ⋮ Optimality regions and fluctuations for Bernoulli last passage models ⋮ A hardness result and new algorithm for the longest common palindromic subsequence problem ⋮ Hardness and approximation of the asynchronous border minimization problem ⋮ Algorithms in the Ultra-Wide Word Model ⋮ Computing a longest common subsequence that is almost increasing on sequences having no repeated elements ⋮ Fast Algorithms for Local Similarity Queries in Two Sequences ⋮ Efficient merged longest common subsequence algorithms for similar sequences ⋮ Fast Algorithms for Computing Tree LCS ⋮ Constrained LCS: Hardness and Approximation ⋮ On the Longest Common Parameterized Subsequence ⋮ Unified compression-based acceleration of edit-distance computation ⋮ A fully compressed algorithm for computing the edit distance of run-length encoded strings ⋮ Calcul de la distance par les sous-mots ⋮ The longest commonly positioned increasing subsequences problem ⋮ String matching with weighted errors ⋮ Quadratic-time algorithm for a string constrained LCS problem ⋮ Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence? ⋮ An O(NP) sequence comparison algorithm ⋮ FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search ⋮ Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems ⋮ Approximate Boyer-Moore string matching for small alphabets ⋮ Fast computation of a longest increasing subsequence and application ⋮ A divide and conquer approach and a work-optimal parallel algorithm for the LIS problem ⋮ An efficient algorithm for LCS problem between two arbitrary sequences ⋮ Faster algorithms for computing longest common increasing subsequences ⋮ Algorithms for computing variants of the longest common subsequence problem ⋮ Edit distance with move operations ⋮ Edit distance with block deletions ⋮ Dynamic edit distance table under a general weighted cost function ⋮ On the generalized constrained longest common subsequence problems ⋮ An improved algorithm for computing the edit distance of run-length coded strings ⋮ Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition ⋮ Fast linear-space computations of longest common subsequences ⋮ Finding the longest common subsequence for multiple biological sequences by ant colony optimization ⋮ A space-efficient alphabet-independent Four-Russians' lookup table and a multithreaded Four-Russians' edit distance algorithm ⋮ An algorithm for matching run-length coded strings ⋮ Constrained sequence analysis algorithms in computational biology ⋮ Efficient algorithms for the longest common subsequence in \(k\)-length substrings ⋮ A practical semi-external memory method for approximate pattern matching ⋮ New efficient algorithms for the LCS and constrained LCS problems ⋮ Faster approximate string matching for short patterns ⋮ Fast searching in packed strings ⋮ Approximate pattern matching with the \(L_1\), \(L_2\) and \(L_\infty\) metrics ⋮ Finding common structured patterns in linear graphs ⋮ The intractability of computing the Hamming distance ⋮ Unnamed Item ⋮ Diversity metrics for direct-coded variable-length chromosome shortest path problem evolutionary algorithms ⋮ Tight conditional lower bounds for longest common increasing subsequence ⋮ LCS approximation via embedding into locally non-repetitive strings ⋮ Efficient algorithms for finding a longest common increasing subsequence ⋮ Fast algorithms for computing tree LCS ⋮ A new efficient algorithm for computing the longest common subsequence ⋮ Semi-local longest common subsequences in subquadratic time ⋮ Communication-Efficient Private Protocols for Longest Common Subsequence ⋮ Shift-or string matching with super-alphabets ⋮ LCS Approximation via Embedding into Local Non-repetitive Strings ⋮ Fast Searching in Packed Strings ⋮ Periodic String Comparison ⋮ New Error Tolerant Method for Search of Long Repeats in DNA Sequences ⋮ An algorithm for distinguishing efficiently bit-strings by their subsequences ⋮ The constrained longest common subsequence problem ⋮ The set-set LCS problem ⋮ On the longest common parameterized subsequence ⋮ Matching for run-length encoded strings ⋮ Efficient error-correcting parsing for (attributed and stochastic) tree grammars ⋮ Complexity measures of words based on string matching and edit distance ⋮ Computing a longest common subsequence for a set of strings ⋮ BIT-PARALLEL COMPUTATION OF LOCAL SIMILARITY SCORE MATRICES WITH UNITARY WEIGHTS ⋮ Fast distance multiplication of unit-Monge matrices ⋮ A fast and practical bit-vector algorithm for the longest common subsequence problem ⋮ Resequencing a set of strings based on a target string ⋮ New algorithms for the LCS problem ⋮ Enumeration of maximal common subsequences between two strings ⋮ A data structure for substring-substring LCS length queries
Cites Work
This page was built for publication: A faster algorithm computing string edit distances
