Longest Common Subsequence with Gap Constraints
From MaRDI portal
Publication:6134862
Abstract: We consider the longest common subsequence problem in the context of subsequences with gap constraints. In particular, following Day et al. 2022, we consider the setting when the distance (i. e., the gap) between two consecutive symbols of the subsequence has to be between a lower and an upper bound (which may depend on the position of those symbols in the subsequence or on the symbols bordering the gap) as well as the case where the entire subsequence is found in a bounded range (defined by a single upper bound), considered by Kosche et al. 2022. In all these cases, we present effcient algorithms for determining the length of the longest common constrained subsequence between two given strings.
Cites work
- scientific article; zbMATH DE number 3495598 (Why is no real title available?)
- scientific article; zbMATH DE number 1962790 (Why is no real title available?)
- scientific article; zbMATH DE number 2051146 (Why is no real title available?)
- scientific article; zbMATH DE number 1512678 (Why is no real title available?)
- scientific article; zbMATH DE number 7561345 (Why is no real title available?)
- scientific article; zbMATH DE number 7297889 (Why is no real title available?)
- scientific article; zbMATH DE number 7056230 (Why is no real title available?)
- scientific article; zbMATH DE number 7650239 (Why is no real title available?)
- A fast algorithm for computing longest common subsequences
- A faster algorithm computing string edit distances
- A longest common subsequence algorithm suitable for similar text strings
- Absent subsequences in words
- Absoluteness of subword inequality is undecidable
- Algorithms for Computing the Longest Parameterized Common Subsequence
- Algorithms for the Longest Common Subsequence Problem
- An algorithm for distinguishing efficiently bit-strings by their subsequences
- An approach to software system modelling and analysis
- Another generalization of abelian equivalence: binomial complexity of infinite words
- Automata theory on sliding windows
- Computing the \(k\)-binomial complexity of the Thue-Morse word
- Connections between subwords and certain matrix mappings
- Consequences of Faster Alignment of Sequences
- Directed acyclic subsequence graph -- overview
- Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
- Generalized Pascal triangle for binomial coefficients of words
- Languages ordered by the subword order
- Longest Common Subsequence with Gap Constraints
- Longest common subsequences of two random sequences
- Multivariate fine-grained complexity of longest common subsequence
- On the index of Simon's congruence for piecewise testability
- Querying regular languages over sliding windows
- Randomized sliding window algorithms for regular languages
- Scattered Factor-Universality of Words
- Searching subsequences
- Software Descriptions with Flow Expressions
- String matching with variable length gaps
- Subsequences in bounded ranges: matching and analysis problems
- Subword histories and Parikh matrices
- Testing Simon's congruence
- The Complexity of Some Problems on Subsequences and Supersequences
- The complexity of downward closure comparisons
- The height of piecewise-testable languages with applications in logical complexity
- The subtrace order and counting first-order logic
- Unshuffling a square is NP-hard
Cited in
(5)
This page was built for publication: Longest Common Subsequence with Gap Constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6134862)
