Longest common subsequence with gap constraints

Duncan Adamson; Paul Sarnighausen-Cahn; Marius Dumitran; Maria Kosche; Tore Koß; Florin Manea; Stefan Siemer

doi:10.1007/s00224-025-10223-0

Longest common subsequence with gap constraints

Duncan Adamson, Paul Sarnighausen-Cahn, Marius Dumitran, Maria Kosche, Tore Koß, Florin Manea, Stefan Siemer^*

^*Corresponding author for this work

School of Computer Science

Research output: Contribution to journal › Article › peer-review

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 efficient algorithms for determining the length of the longest common constrained subsequence between two given strings, and discuss lower bounds for the respective problems.

Original language	English
Article number	25
Pages (from-to)	1-39
Number of pages	39
Journal	Theory of Computing Systems
Volume	69
Issue number	2
DOIs	https://doi.org/10.1007/s00224-025-10223-0
Publication status	Published - 6 Jun 2025

Keywords

Bounded range
Fine grained complexity
Gap constraints
Longest common subsequence

Access to Document

10.1007/s00224-025-10223-0

Adamson-et-al-2025-Longest-commons-subsequence-TheoryCompSysm-69-25-CCBY
Copyright © The Author(s) 2025. This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Final published version, 806 KBLicence: CC BY

Cite this

@article{f1eb3b377baa416eb3e49ef3986b1074,

title = "Longest common subsequence with gap constraints",

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 efficient algorithms for determining the length of the longest common constrained subsequence between two given strings, and discuss lower bounds for the respective problems.",

keywords = "Bounded range, Fine grained complexity, Gap constraints, Longest common subsequence",

author = "Duncan Adamson and Paul Sarnighausen-Cahn and Marius Dumitran and Maria Kosche and Tore Ko{\ss} and Florin Manea and Stefan Siemer",

note = "Funding: The work on the current article was partly supported by the German Research Foundation (DFG) [project numbers 389613931 (research grant); 466789228 (Heisenberg grant)]. Open Access funding enabled and organized by Projekt DEAL.",

year = "2025",

month = jun,

day = "6",

doi = "10.1007/s00224-025-10223-0",

language = "English",

volume = "69",

pages = "1--39",

journal = "Theory of Computing Systems",

issn = "1432-4350",

publisher = "Springer",

number = "2",

}

TY - JOUR

T1 - Longest common subsequence with gap constraints

AU - Adamson, Duncan

AU - Sarnighausen-Cahn, Paul

AU - Dumitran, Marius

AU - Kosche, Maria

AU - Koß, Tore

AU - Manea, Florin

AU - Siemer, Stefan

N1 - Funding: The work on the current article was partly supported by the German Research Foundation (DFG) [project numbers 389613931 (research grant); 466789228 (Heisenberg grant)]. Open Access funding enabled and organized by Projekt DEAL.

PY - 2025/6/6

Y1 - 2025/6/6

N2 - 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 efficient algorithms for determining the length of the longest common constrained subsequence between two given strings, and discuss lower bounds for the respective problems.

AB - 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 efficient algorithms for determining the length of the longest common constrained subsequence between two given strings, and discuss lower bounds for the respective problems.

KW - Bounded range

KW - Fine grained complexity

KW - Gap constraints

KW - Longest common subsequence

U2 - 10.1007/s00224-025-10223-0

DO - 10.1007/s00224-025-10223-0

M3 - Article

AN - SCOPUS:105007446907

SN - 1432-4350

VL - 69

SP - 1

EP - 39

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 2

M1 - 25

ER -

Longest common subsequence with gap constraints

Abstract

Keywords

Access to Document

Fingerprint

Cite this