A fast algorithm for computing longest common subsequences
From MaRDI portal
Publication:4125781
DOI10.1145/359581.359603zbMath0354.68078OpenAlexW2027506564WikidataQ56004217 ScholiaQ56004217MaRDI QIDQ4125781
Thomas G. Szymanski, James W. Hunt
Publication date: 1977
Published in: Communications of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/359581.359603
Related Items (only showing first 100 items - show all)
A common basis for similarity measures involving two strings† ⋮ A branch-and-cut approach to the repetition-free longest common subsequence problem ⋮ Palindromic subsequence automata and longest common palindromic subsequence ⋮ Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings ⋮ Performance analysis of some simple heuristics for computing longest common subsequences ⋮ A fast algorithm for computing a longest common increasing subsequence ⋮ Longest increasing subsequences in sliding windows ⋮ Enumerating longest increasing subsequences and patience sorting ⋮ Order-preserving pattern matching with \(k\) mismatches ⋮ The Complexity of Problems in P Given Correlated Instances ⋮ Speeding up transposition-invariant string matching ⋮ A multiobjective optimization algorithm for the weighted LCS ⋮ 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 ⋮ Searching subsequences ⋮ A novel look-ahead optimization strategy for trie-based approximate string matching ⋮ Data structures and algorithms for approximate string matching ⋮ Two algorithms for LCS consecutive suffix alignment ⋮ A lower bound for the edit-distance problem under an arbitrary cost function ⋮ Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism ⋮ Space-Efficient Algorithms for Longest Increasing Subsequence ⋮ The generalized definitions of the two-dimensional largest common substructure problems ⋮ Computing a longest common subsequence that is almost increasing on sequences having no repeated elements ⋮ Efficient merged longest common subsequence algorithms for similar sequences ⋮ Fast Algorithms for Computing Tree LCS ⋮ On the Longest Common Parameterized Subsequence ⋮ Fast algorithms for computing the constrained LCS of run-length encoded strings ⋮ Calcul de la distance par les sous-mots ⋮ The string merging problem ⋮ A fast algorithm for the longest-common-subsequence problem ⋮ Empirical scaling of the length of the longest increasing subsequences of random walks ⋮ An O(NP) sequence comparison algorithm ⋮ FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search ⋮ 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 ⋮ An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints ⋮ Faster algorithms for computing longest common increasing subsequences ⋮ Computational geometry algorithms for the systolic screen ⋮ An \(A^\ast\) search algorithm for the constrained longest common subsequence problem ⋮ Algorithms for computing variants of the longest common subsequence problem ⋮ On the inadequacy of tournament algorithms for the \(N\)-SCS problem ⋮ Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion ⋮ On the generalized constrained longest common subsequence problems ⋮ New clique and independent set algorithms for circle graphs ⋮ On locally Gabriel geometric graphs ⋮ Fast linear-space computations of longest common subsequences ⋮ Dynamic programming with convexity, concavity and sparsity ⋮ Space-efficient algorithms for longest increasing subsequence ⋮ Handling precedence constraints in scheduling problems by the sequence pair representation ⋮ A large neighborhood search heuristic for the longest common subsequence problem ⋮ An algorithm for matching run-length coded strings ⋮ A bit-string longest-common-subsequence algorithm ⋮ Constrained sequence analysis algorithms in computational biology ⋮ Finding the gapped longest common subsequence by incremental suffix maximum queries ⋮ Efficient algorithms for the longest common subsequence in \(k\)-length substrings ⋮ New efficient algorithms for the LCS and constrained LCS problems ⋮ Efficient algorithms for the block edit problems ⋮ An all-substrings common subsequence algorithm ⋮ Maximum \(k\)-covering of weighted transitive graphs with applications ⋮ Finding a longest common subsequence between a run-length-encoded string and an uncompressed string ⋮ Circular permutation graph family with applications ⋮ Content-dependent chunking for differential compression, the local maximum approach ⋮ Finding common structured patterns in linear graphs ⋮ A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings ⋮ Design and implementation of an efficient priority queue ⋮ Fixed-parameter tractability results for feedback set problems in tournaments ⋮ Unnamed Item ⋮ Tight conditional lower bounds for longest common increasing subsequence ⋮ Edit distance-based kernel functions for structural pattern classification ⋮ Finding longest increasing and common subsequences in streaming data ⋮ LCS approximation via embedding into locally non-repetitive strings ⋮ A sparse dynamic programming algorithm for alignment with non-overlapping inversions ⋮ Unnamed Item ⋮ An information-theoretic lower bound for the longest common subsequence problem ⋮ Rank tests from partially ordered data using importance and MCMC sampling methods ⋮ 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 ⋮ A review of data mining applications in crime ⋮ LCS Approximation via Embedding into Local Non-repetitive Strings ⋮ A diagonal-based algorithm for the longest common increasing subsequence problem ⋮ Sparse LCS common substring alignment ⋮ Computing the longest topological common subsequence of a symbol-wise totally ordered directed acyclic graph and a sequence ⋮ The longest almost-increasing subsequence ⋮ On the longest common parameterized subsequence ⋮ An almost-linear time and linear space algorithm for the longest common subsequence problem ⋮ Computing a longest common subsequence for a set of strings ⋮ Multi-subsequence searching ⋮ Automatic error correction in flexion languages ⋮ A systolic array for the longest common subsequence problem ⋮ APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ † ⋮ New algorithms for the LCS problem ⋮ Enumeration of maximal common subsequences between two strings ⋮ Fast and longest rollercoasters ⋮ A data structure for substring-substring LCS length queries ⋮ A space efficient algorithm for the longest common subsequence in \(k\)-length substrings
This page was built for publication: A fast algorithm for computing longest common subsequences
