论文标题
有限范围的子序列：匹配和分析问题
Subsequences in Bounded Ranges: Matching and Analysis Problems
论文作者
论文摘要
在本文中，我们考虑了检查给定单词$ v $是否是另一个单词$ w $的子序列的经典算法问题的变体。更确切地说，我们考虑了决定的问题，考虑到数字$ p $（定义了一个范围）和两个单词$ v $和$ w $，无论是否存在因子$ W [i：i+p-1] $（或者，换句话说，$ w $的长度$ p $）的$ w $ a $ v $ a $ v $ a in Specence（i。\，e。 $ W [i：i+p-1] $）。对于此问题的时间复杂性，我们给出了匹配的上和下二次界限。此外，我们考虑了在这种情况下的一系列算法问题，其中，对于给定的整数$ k $，$ p $和一个单词$ w $，我们分析了所有长度$ k $单词的套装$ p $ -subseq $ _ {k}（w）$，这些$ k $的$ k $，这是一定长度$ p $ $ w $的sequesence。其中，我们考虑了$ k $ - 大学性问题，$ k $ - 等价问题以及与缺席子序列有关的问题。令人惊讶的是，与单词的经典模型不同，这些问题通常具有有效的解决方案，我们表明，当考虑有限范围的子序列时，这些问题中的大多数在新环境中变得棘手。最后，我们提供了一个示例，说明如何将某些结果应用于圆形单词的子序列匹配问题。
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.
