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.