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₁ uf is an f-segmental subsequence of a string v₀u₁v₁ ufvf. 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-segmental subsequence problem and the f-segmental subsequence matching problem. The former asks the longest string that is an fᵢ-segmental subsequence of two input strings Tᵢ 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.