A fast algorithm for computing longest common subsequences

Cited in

(only showing first 100 items - show all)

Sparse LCS common substring alignment
Computing the longest topological common subsequence of a symbol-wise totally ordered directed acyclic graph and a sequence
On the longest common parameterized subsequence
An almost-linear time and linear space algorithm for the longest common subsequence problem
A systolic array 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
Data structures and algorithms for approximate string matching
A lower bound for the edit-distance problem under an arbitrary cost function
The string merging problem
A fast algorithm for the longest-common-subsequence problem
Computational geometry algorithms for the systolic screen
On the inadequacy of tournament algorithms for the N-SCS problem
New clique and independent set algorithms for circle graphs
Fast linear-space computations of longest common subsequences
Dynamic programming with convexity, concavity and sparsity
Maximum \(k\)-covering of weighted transitive graphs with applications
Circular permutation graph family with applications
An information-theoretic lower bound for the longest common subsequence problem
Performance analysis of some simple heuristics for computing longest common subsequences
Multi-subsequence searching
Efficient merged longest common subsequence algorithms for similar sequences
An efficient algorithm for LCS problem between two arbitrary sequences
Rank tests from partially ordered data using importance and MCMC sampling methods
Longest increasing subsequences in sliding windows
Fast approximate matching of words against a dictionary
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
Space-efficient algorithms for longest increasing subsequence
A bit-string longest-common-subsequence algorithm
Enumeration of maximal common subsequences between two strings
Fast and longest rollercoasters
A data structure for substring-substring LCS length queries
The generalized definitions of the two-dimensional largest common substructure problems
An \(A^\ast\) search algorithm for the constrained longest common subsequence problem
Finding the gapped longest common subsequence by incremental suffix maximum queries
Efficient algorithms for the longest common subsequence in \(k\)-length substrings
Fixed-parameter tractability results for feedback set problems in tournaments
Tight conditional lower bounds for longest common increasing subsequence
A diagonal-based algorithm for the longest common increasing subsequence problem
A space efficient algorithm for the longest common subsequence in \(k\)-length substrings
Palindromic subsequence automata and longest common palindromic subsequence
Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism
A divide and conquer approach and a work-optimal parallel algorithm for the LIS problem
An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints
An all-substrings common subsequence algorithm
Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
Edit distance-based kernel functions for structural pattern classification
Finding longest increasing and common subsequences in streaming data
Searching subsequences
Two algorithms for LCS consecutive suffix alignment
A branch-and-cut approach to the repetition-free longest common subsequence problem
Enumerating longest increasing subsequences and patience sorting
Order-preserving pattern matching with \(k\) mismatches
Empirical scaling of the length of the longest increasing subsequences of random walks
A multiobjective optimization algorithm for the weighted LCS
New tabulation and sparse dynamic programming based techniques for sequence similarity problems
A new practical linear space algorithm for the longest common subsequence problem
Space-efficient algorithms for longest increasing subsequence
Fast Algorithms for Computing Tree LCS
On the Longest Common Parameterized Subsequence
LCS Approximation via Embedding into Local Non-repetitive Strings
Calcul de la distance par les sous-mots
A common basis for similarity measures involving two strings†
Computing a longest common subsequence that is almost increasing on sequences having no repeated elements
Design and implementation of an efficient priority queue
APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ †
Fast algorithms for computing the constrained LCS of run-length encoded strings
The Complexity of Problems in P Given Correlated Instances
A sparse dynamic programming algorithm for alignment with non-overlapping inversions
Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
On the generalized constrained longest common subsequence problems
A review of data mining applications in crime
On locally Gabriel geometric graphs
Fast and longest rollercoasters
Sketching, streaming, and fine-grained complexity of (weighted) LCS
Longest common subsequences
Approximating longest common subsequence in linear time: beating the \(\sqrt{n}\) barrier
Tight conditional lower bounds for longest common increasing subsequence
Handling precedence constraints in scheduling problems by the sequence pair representation
An algorithm and applications to sequence alignment with weighted constraints
Constrained sequence analysis algorithms in computational biology
A learning algorithm for the longest common subsequence problem
A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence
Linear-space S-table algorithms for the longest common subsequence problem
Computing longest Lyndon subsequences and longest common Lyndon subsequences
Longest Common Subsequence with Gap Constraints
Subsequences in bounded ranges: matching and analysis problems
Polynomial-delay enumeration of maximal common subsequences
Faster algorithms for computing longest common increasing subsequences
The longest almost increasing subsequence problem with sliding windows
Ulam's metric in higher dimensions
An algorithm for matching run-length coded strings
k-universality of regular languages revisited
Longest common subsequence with gap constraints
The generalized constrained longest common subsequence in the run-length encoded format
Efficient algorithms for enumerating maximal common subsequences of two strings

This page was built for publication: A fast algorithm for computing longest common subsequences

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