In this paper, we consider a variant of the classical algorithmic problem of checking whether a given word $v$ is a subsequence of another word $w$. More precisely, we consider the problem of deciding, given a number $p$ (defining a range-bound) and two words $v$ and $w$, whether there exists a factor $w[i:i+p-1]$ (or, in other words, a range of length $p$) of $w$ having $v$ as subsequence (i.\,e., $v$ occurs as a subsequence in the bounded range $w[i:i+p-1]$). We give matching upper and lower quadratic bounds for the time complexity of this problem. Further, we consider a series of algorithmic problems in this setting, in which, for given integers $k$, $p$ and a word $w$, we analyse the set $p$-Subseq$_{k}(w)$ of all words of length $k$ which occur as subsequence of some factor of length $p$ of $w$. Among these, we consider the $k$-universality problem, the $k$-equivalence problem, as well as problems related to absent subsequences. Surprisingly, unlike the case of the classical model of subsequences in words where such problems have efficient solutions in general, we show that most of these problems become intractable in the new setting when subsequences in bounded ranges are considered. Finally, we provide an example of how some of our results can be applied to subsequence matching problems for circular words.
翻译:在本文中, 我们考虑一个典型的算法问题的变式, 即检查给定的单词$v$是否是另一个单词的子序列。 更确切地说, 我们考虑的是一个问题, 考虑到一个数美元( 限定范围) 和两个字美元和元美元, 是否存在一个因数$[ i: +p-1] (或, 换句话说, 长度范围为美元), 以美元作为子序列( i.\, e., 美元作为下序列。 美元作为下序列的子序列。 我们给出了这个问题的时间复杂性对应的上下四边框。 此外, 我们考虑了一系列的算法问题, 对于给定的整数美元、 美元和一字, 我们分析的设定值为美元- supersequalqueme 。 当我们从一个正序的次序列中, 当我们从一个因数的次序到一个因子问题 美元, 当我们从一个直径的次序中, 当我们从一个因数的直值中, 质的直值问题 质的个次的个数, 当我们算为美元 。 问题在直序的次的个次的个次折号中, 问题是如何的次的次的 。