Algorithms for the Longest Common Subsequence Problem

Cited in

(only showing first 100 items - show all)

The constrained longest common subsequence problem
Sparse LCS common substring alignment
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
A lower bound for the edit-distance problem under an arbitrary cost function
A fast algorithm for the longest-common-subsequence problem
Efficient recognition of rational relations
Computational geometry algorithms for the systolic screen
On the inadequacy of tournament algorithms for the N-SCS problem
Fast linear-space computations of longest common subsequences
Dynamic programming with convexity, concavity and sparsity
An information-theoretic lower bound for the longest common subsequence problem
Some limit results for longest common subsequences
Parallel algorithms for permutation graphs
Performance analysis of some simple heuristics for computing longest common subsequences
Simple and fast linear space computation of longest common subsequences
A substring-substring LCS data structure
On finding a longest common palindromic subsequence
An efficient algorithm for LCS problem between two arbitrary sequences
Comparison of strings belonging to the same family
The longest common subsequence problem for sequences with nested arc annotations.
TS-CHIEF: a scalable and accurate forest algorithm for time series classification
A bit-string longest-common-subsequence algorithm
Enumeration of maximal common subsequences between two strings
Computing longest (common) Lyndon subsequences
Exact algorithms for the repetition-bounded longest common subsequence problem
Computing a longest common almost-increasing subsequence of two sequences
Tight conditional lower bounds for longest common increasing subsequence
Maximal common subsequence algorithms
Resequencing a set of strings based on a target string
Algorithms for subsequence combinatorics
Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism
A simple algorithm for the constrained sequence problems
An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints
Multiple genome rearrangement by swaps and by element duplications
Algorithms for the bounded set-up knapsack problem
Similar sequence matching supporting variable-length and variable-tolerance continuous queries on time-series data stream
Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
Finding longest increasing and common subsequences in streaming data
Two algorithms for LCS consecutive suffix alignment
A new practical linear space algorithm for the longest common subsequence problem
Fast Algorithms for Computing Tree LCS
Constrained LCS: Hardness and Approximation
LCS Approximation via Embedding into Local Non-repetitive Strings
Sparse RNA Folding: Time and Space Efficient Algorithms
Calcul de la distance par les sous-mots
A common basis for similarity measures involving two strings†
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
DERIVING A FAST SYSTOLIC ALGORITHM FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM
Context prediction of mobile users based on time-inferred pattern networks: a probabilistic approach
On the approximation of shortest common supersequences and longest common subsequences
Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
On the generalized constrained longest common subsequence problems
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
Maximal common subsequence algorithms
Fitness landscape analysis for the no-wait flow-shop scheduling problem
Sparse RNA folding: time and space efficient algorithms
The similarity of two strings of fuzzy sets.
Concordance and consensus
A learning algorithm for the longest common subsequence problem
Fast prefix matching of bounded strings
ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
Efficient reconstruction of sequences from their subsequences of supersequences
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
Longest bordered and periodic subsequences
A novel distance measure based on dynamic time warping to improve time series classification
Subsequence frequency in binary words
Polynomial-delay enumeration of maximal common subsequences
Polynomial-time equivalences and refined algorithms for longest common subsequence variants
k-universality of regular languages revisited
A compact DAG for storing and searching maximal common subsequences
Longest common subsequence with gap constraints
The generalized constrained longest common subsequence in the run-length encoded format
The longest common subsequence problem for small alphabets in the word RAM model
LCS approximation via embedding into locally non-repetitive strings
A linear-time \(n^{0.4}\)-approximation for longest common subsequence
Longest common substring with gaps and related problems
On finding longest palindromic subsequences using longest common subsequences
Subsequence matching and analysis problems for formal languages
Linear time subsequence and supersequence regex matching
Fast algorithms for computing tree LCS
A new efficient algorithm for computing the longest common subsequence
On the decoding error weight of one or two deletion channels
Computing a longest common subsequence for a set of strings
Automatic error correction in flexion languages
Scaled and permuted string matching
Calculating distances for dissimilar strings: the shortest path formulation revisited
Longest common subsequence problem for unoriented and cyclic strings

This page was built for publication: Algorithms for the Longest Common Subsequence Problem

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