Subsequence Pattern Matching with Segment Number Constraint
<|reference_start|>Subsequence Pattern Matching with Segment Number Constraint: This paper is concerned with subsequences that consist of limited numbers of segments. We call a subsequence {$f$-segmental} if it is composed of $f$ factors. More precisely, any string of the form $u_1 \dots u_f$ is an $f$-segmental subsequence of a string $v_0u_1v_1 \dots u_fv_f$. Since factors are $1$-segmental subsequences, this relativizes the notions of factors and subsequences. This paper studies some basic problems concerning $f$-segmental subsequences: namely, the longest common $(f_1,f_2)$-segmental subsequence problem and the $f$-segmental subsequence matching problem. The former asks the longest string that is an $f_i$-segmental subsequence of two input strings $T_i$ with $i=1,2$. The latter asks whether an input string $P$ is an $f$-segmental subsequence of the other input string $T$. We present polynomial-time algorithms for those problems and show that the one for the $f$-segmental subsequence matching problem is optimal modulo sub-polynomial factors under the strong exponential-time hypothesis.<|reference_end|>
@article{yonemoto2024subsequence,
    title={Subsequence Pattern Matching with Segment Number Constraint},
    author={Yuki Yonemoto, Takuya Mieno, Shunsuke Inenaga, Ryo Yoshinaka, and
  Ayumi Shinohara},
    journal={arXiv preprint arXiv:2407.19796},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.19796},
    primaryClass={cs.DS}
}