Scholarlink

The longest common subsequence (LCS) is a fundamental problem in string processing which has numerous algorithmic studies, extensions, and applications. A sequence \(u_1, \ldots , u_f\) of f strings is said to be an (f-)segmentation of a string P if \(P = u_1 \cdots u_f\) . Li et al. [BIBM 2022] proposed a new variant of the LCS problem for given strings \(T_1, T_2\) 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 \(T_1\) and \(T_2\) . Li et al. [IJTCS-FAW 2024] gave a dynamic programming solution that solves SegLCS in \(O(fn_1n_2)\) time with \(O(fn_1 + n_2)\) space, where \(n_1 = |T_1|\) , \(n_2 = |T_2|\) , and \(n_1 \le n_2\) . Recently, Banerjee et al. [ESA 2024] presented an algorithm which, for a constant \(f \ge 3\) , solves SegLCS in \(\tilde{O}((n_1n_2)^{1-(1/3)^{f-2}})\) time ( \(\tilde{O}(\cdot )\) suppresses polylogarithmic factors). 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:

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Subsequence Matching and LCS with Segment Number Constraints

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Yuki Yonemoto,
  • Takuya Mieno,
  • Shunsuke Inenaga,
  • Ryo Yoshinaka,
  • Ayumi Shinohara

摘要

The longest common subsequence (LCS) is a fundamental problem in string processing which has numerous algorithmic studies, extensions, and applications. A sequence \(u_1, \ldots , u_f\) of f strings is said to be an (f-)segmentation of a string P if \(P = u_1 \cdots u_f\) . Li et al. [BIBM 2022] proposed a new variant of the LCS problem for given strings \(T_1, T_2\) 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 \(T_1\) and \(T_2\) . Li et al. [IJTCS-FAW 2024] gave a dynamic programming solution that solves SegLCS in \(O(fn_1n_2)\) time with \(O(fn_1 + n_2)\) space, where \(n_1 = |T_1|\) , \(n_2 = |T_2|\) , and \(n_1 \le n_2\) . Recently, Banerjee et al. [ESA 2024] presented an algorithm which, for a constant \(f \ge 3\) , solves SegLCS in \(\tilde{O}((n_1n_2)^{1-(1/3)^{f-2}})\) time ( \(\tilde{O}(\cdot )\) suppresses polylogarithmic factors). 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: