A linear space algorithm for computing maximal common subsequences
From MaRDI portal
Publication:4055176
DOI10.1145/360825.360861zbMath0301.68042DBLPjournals/cacm/Hirschberg75OpenAlexW2165654401WikidataQ55891301 ScholiaQ55891301MaRDI QIDQ4055176
Publication date: 1975
Published in: Communications of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/360825.360861
Related Items (only showing first 100 items - show all)
A common basis for similarity measures involving two strings† ⋮ Formal timing analysis for distributed real-time programs ⋮ Using Hirschberg's algorithm to generate random alignments of strings ⋮ 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 faster linear systolic algorithm for recovering a longest common subsequence ⋮ LCS\(k\): a refined similarity measure ⋮ A linear space algorithm for computing a longest common increasing subsequence ⋮ Dynamic programming algorithms for the mosaic longest common subsequence problem ⋮ Efficient algorithms for regular expression constrained sequence alignment ⋮ Efficient algorithms for finding interleaving relationship between sequences ⋮ The longest common subsequence problem revisited ⋮ Constrained string editing ⋮ An \(O(ND)\) difference algorithm and its variations ⋮ Asynchronous communication model based on linear logic ⋮ The set LCS problem ⋮ Sequence comparison with concave weighting functions ⋮ A novel look-ahead optimization strategy for trie-based approximate string matching ⋮ RNA multiple structural alignment with longest common subsequences ⋮ Data structures and algorithms for approximate string matching ⋮ Linear-space algorithms that build local alignments from fragments ⋮ Calculating distances for dissimilar strings: the shortest path formulation revisited ⋮ Multi-sided boundary labeling ⋮ A hybrid dynamic programming and memetic algorithm to the traveling salesman problem with hotel selection ⋮ Two applications of the divide \(\&\) conquer principle in the molecular sciences ⋮ A faster reduction of the dynamic time warping distance to the longest increasing subsequence length ⋮ Longest common subsequence in sublinear space ⋮ Optimality regions and fluctuations for Bernoulli last passage models ⋮ The generalized definitions of the two-dimensional largest common substructure problems ⋮ One-dimensional approximate point set pattern matching with \(L_p\)-norm ⋮ Hardness and approximation of the asynchronous border minimization problem ⋮ Efficient merged longest common subsequence algorithms for similar sequences ⋮ A faster algorithm computing string edit distances ⋮ Strategy-proof social choice on multiple and multi-dimensional single-peaked domains ⋮ Fast Algorithms for Computing Tree LCS ⋮ Constrained LCS: Hardness and Approximation ⋮ A fully compressed algorithm for computing the edit distance of run-length encoded strings ⋮ Orphan gene finding -- an exon assembly approach. ⋮ Sequence Alignment Algorithms for Run-Length-Encoded Strings ⋮ Exact algorithms for the repetition-bounded longest common subsequence problem ⋮ The string merging problem ⋮ A fast algorithm for the longest-common-subsequence problem ⋮ A parallel strategy for biological sequence alignment in restricted memory space ⋮ On a cyclic string-to-string correction problem ⋮ A hyper-heuristic for the longest common subsequence problem ⋮ An O(NP) sequence comparison algorithm ⋮ Minimum message length encoding and the comparison of macromolecules ⋮ FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search ⋮ On measuring similarity for sequences of itemsets ⋮ An overview on XML similarity: background, current trends and future directions ⋮ An efficient algorithm for LCS problem between two arbitrary sequences ⋮ Faster algorithms for computing longest common increasing subsequences ⋮ Space efficient algorithms for ordered tree comparison ⋮ On the inadequacy of tournament algorithms for the \(N\)-SCS problem ⋮ Breadth-first heuristic search ⋮ An adaptive multi-policy grid service for biological sequence comparison ⋮ Parallel parsing on a one-way linear array of finite-state machines ⋮ Dynamic edit distance table under a general weighted cost function ⋮ On the generalized constrained longest common subsequence problems ⋮ On the space complexity of some algorithms for sequence comparison ⋮ Sequence alignment with arbitrary steps and further generalizations, with applications to alignments in linguistics ⋮ An improved algorithm for computing the edit distance of run-length coded strings ⋮ A time-efficient, linar-space local similarity algorithm ⋮ Comparing bacterial genomes from linear orders of patterns ⋮ Fast linear-space computations of longest common subsequences ⋮ Dynamic programming with convexity, concavity and sparsity ⋮ A large neighborhood search heuristic for the longest common subsequence problem ⋮ Finding the gapped longest common subsequence by incremental suffix maximum queries ⋮ A practical semi-external memory method for approximate pattern matching ⋮ Sparse RNA folding: time and space efficient algorithms ⋮ An all-substrings common subsequence algorithm ⋮ An improved algorithm for the longest common subsequence problem ⋮ Identifying periodic occurrences of a template with applications to protein structure ⋮ Constrained sequence alignment ⋮ The intractability of computing the Hamming distance ⋮ Unnamed Item ⋮ An information-theoretic lower bound for the longest common subsequence problem ⋮ Table design in dynamic programming ⋮ Fast algorithms for computing tree LCS ⋮ The cache complexity of multithreaded cache oblivious algorithms ⋮ Approximate labelled subtree homeomorphism ⋮ Sparse RNA Folding: Time and Space Efficient Algorithms ⋮ New Error Tolerant Method for Search of Long Repeats in DNA Sequences ⋮ A diagonal-based algorithm for the longest common increasing subsequence problem ⋮ Comparison of strings belonging to the same family ⋮ Computing the longest topological common subsequence of a symbol-wise totally ordered directed acyclic graph and a sequence ⋮ Reconstructing a history of recombinations from a set of sequences ⋮ The set-set LCS problem ⋮ Matching for run-length encoded strings ⋮ An almost-linear time and linear space algorithm for the longest common subsequence problem ⋮ On computing all suboptimal alignments ⋮ Computing a longest common subsequence for a set of strings ⋮ Multi-subsequence searching ⋮ Simple and fast linear space computation of longest common subsequences ⋮ From regular expression matching to parsing ⋮ Automatic error correction in flexion languages ⋮ A simple and space-efficient fragment-chaining algorithm for alignment of DNA and protein sequences ⋮ A fast and practical bit-vector algorithm for the longest common subsequence problem ⋮ New algorithms for the LCS problem ⋮ A space efficient algorithm for the longest common subsequence in \(k\)-length substrings
This page was built for publication: A linear space algorithm for computing maximal common subsequences
