2024/07/29 by Yuki Yonemoto, Takuya Mieno, Yonemoto, Yuki +7
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning in Bioinformatics #Network Packet Processing and Optimization
paper · pdf · doi:10.48550/arxiv.2407.19796
openalex publication_date 2024/07/29 · openalex created_date 2024/08/01 · openalex updated_date 2026/07/28
The longest common subsequence (LCS) is a fundamental problem in string processing which has numerous algorithmic studies, extensions, and applications. A sequence u1, …, uf of f strings s said to be an (f-)segmentation of a string P if P = u1 ⋯ uf. Li et al. [BIBM 2022] proposed a new variant of the LCS problem for given strings T1, T2 and an integer f, which we hereby call the segmental LCS problem (SegLCS), of finding (the length of) a longest string P that has an f-segmentation which can be embedded into both T1 and T2. Li et al. [IJTCS-FAW 2024] gave a dynamic programming solution that solves SegLCS in O(fn1n2) time with O(fn1 + n2) space, where n1 = |T1|, n2 = |T2|, and n1 ≤ n2. Recently, Banerjee et al. [ESA 2024] presented an algorithm which, for a constant f ≥ 3, solves SegLCS in O((n1n2)^1-(1/3)f-2) time. In this paper, we deal with SegLCS as well as the problem of segmental subsequence pattern matching, SegE, that asks to determine whether a pattern P of length m has an f-segmentation that can be embedded into a text T of length n. When f = 1, this is equivalent to substring matching, and when f = |P|, this is equivalent to subsequence matching. Our focus in this article is the case of general values of f, and our main contributions are threefold: (1) O((mn)1-ε)-time conditional lower bound for SegE under the strong exponential-time hypothesis (SETH), for any constant ε> 0. (2) O(mn)-time algorithm for SegE. (3) O(fn2(n1 - ℓ+1))-time algorithm for SegLCS where ℓ is the solution length.