A linear space algorithm for computing maximal common subsequences

Cited in

(only showing first 100 items - show all)

Approximate labelled subtree homeomorphism
Computing the longest topological common subsequence of a symbol-wise totally ordered directed acyclic graph and a sequence
An almost-linear time and linear space algorithm for the longest common subsequence problem
New algorithms for the LCS problem
Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
The longest common subsequence problem revisited
Constrained string editing
An \(O(ND)\) difference algorithm and its variations
The set LCS problem
Sequence comparison with concave weighting functions
Data structures and algorithms for approximate string matching
A faster algorithm computing string edit distances
The string merging problem
A fast algorithm for the longest-common-subsequence problem
On the inadequacy of tournament algorithms for the N-SCS problem
Parallel parsing on a one-way linear array of finite-state machines
On the space complexity of some algorithms for sequence comparison
A time-efficient, linar-space local similarity algorithm
Fast linear-space computations of longest common subsequences
Dynamic programming with convexity, concavity and sparsity
Identifying periodic occurrences of a template with applications to protein structure
Constrained sequence alignment
An information-theoretic lower bound for the longest common subsequence problem
Reconstructing a history of recombinations from a set of sequences
Matching for run-length encoded strings
On computing all suboptimal alignments
Formal timing analysis for distributed real-time programs
Using Hirschberg's algorithm to generate random alignments of strings
Performance analysis of some simple heuristics for computing longest common subsequences
Two applications of the divide \(\&\) conquer principle in the molecular sciences
Orphan gene finding -- an exon assembly approach.
Multi-subsequence searching
Simple and fast linear space computation of longest common subsequences
A fast and practical bit-vector algorithm for the longest common subsequence problem
A hybrid dynamic programming and memetic algorithm to the traveling salesman problem with hotel selection
Optimality regions and fluctuations for Bernoulli last passage models
Hardness and approximation of the asynchronous border minimization problem
Efficient merged longest common subsequence algorithms for similar sequences
On measuring similarity for sequences of itemsets
An efficient algorithm for LCS problem between two arbitrary sequences
An improved algorithm for the longest common subsequence problem
Comparison of strings belonging to the same family
The set-set LCS problem
A simple and space-efficient fragment-chaining algorithm for alignment of DNA and protein sequences
Asynchronous communication model based on linear logic
Linear-space algorithms that build local alignments from fragments
A fully compressed algorithm for computing the edit distance of run-length encoded strings
FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search
From regular expression matching to parsing
A faster reduction of the dynamic time warping distance to the longest increasing subsequence length
The generalized definitions of the two-dimensional largest common substructure problems
Exact algorithms for the repetition-bounded longest common subsequence problem
Finding the gapped longest common subsequence by incremental suffix maximum queries
A diagonal-based algorithm for the longest common increasing subsequence problem
A space efficient algorithm for the longest common subsequence in \(k\)-length substrings
Efficient algorithms for regular expression constrained sequence alignment
Efficient algorithms for finding interleaving relationship between sequences
RNA multiple structural alignment with longest common subsequences
Breadth-first heuristic search
An all-substrings common subsequence algorithm
Table design in dynamic programming
Longest common subsequence in sublinear space
New Error Tolerant Method for Search of Long Repeats in DNA Sequences
A faster linear systolic algorithm for recovering a longest common subsequence
LCSk: a refined similarity measure
A new practical linear space algorithm for the longest common subsequence problem
Multi-sided boundary labeling
Fast Algorithms for Computing Tree LCS
Constrained LCS: Hardness and Approximation
Sequence Alignment Algorithms for Run-Length-Encoded Strings
Sparse RNA Folding: Time and Space Efficient Algorithms
One-dimensional approximate point set pattern matching with L_p-norm
A common basis for similarity measures involving two strings†
APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ †
A parallel strategy for biological sequence alignment in restricted memory space
A hyper-heuristic for the longest common subsequence problem
DERIVING A FAST SYSTOLIC ALGORITHM FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM
An overview on XML similarity: background, current trends and future directions
Dynamic edit distance table under a general weighted cost function
On the generalized constrained longest common subsequence problems
Finding many optimal paths without growing any optimal path trees
Sequence alignment with arbitrary steps and further generalizations, with applications to alignments in linguistics
Exact Multiple Sequence Alignment by Synchronized Decision Diagrams
The one-way communication complexity of dynamic time warping distance
From Regular Expression Matching to Parsing
Longest common subsequences
Approximating longest common subsequence in linear time: beating the \(\sqrt{n}\) barrier
An algorithm and applications to sequence alignment with weighted constraints
A practical semi-external memory method for approximate pattern matching
Sparse RNA folding: time and space efficient algorithms
A learning algorithm for the longest common subsequence problem
The intractability of computing the Hamming distance
ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
Weighted LCS
scientific article; zbMATH DE number 7765364 (Why is no real title available?)
Absent Subsequences in Words
Linear-space S-table algorithms for the longest common subsequence problem
Longest bordered and periodic subsequences
Space-efficient STR-IC-LCS computation
Shuffle squares and reverse shuffle squares

This page was built for publication: A linear space algorithm for computing maximal common subsequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4055176)