Inferring Strings from Runs
Inferring Strings from Runs
复制标题
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Wataru Matsubara;A. Ishino;A. Shinohara
中科院分区：
文献类型：
--
作者：
Wataru Matsubara;A. Ishino;A. Shinohara
． 字符串中的运行是字符串中不可扩展的周期子字符串。从理论和实践的角度来看，检测管柱中的所有下入都是非常重要的。在本文中，我们考虑了它的反向问题。我们揭示了时间复杂度取决于要输出的字符串的字母表大小k。我们证明了它对于二进制字母表和无限字母表都在多项式时间内可解，而对于有限k≥4它是np完全的。我们还考虑了该问题的一个变体，其中只给出运行的子集作为输入。我们证明了对于无限字母，它在多项式时间内可解，而对于有限k≥3，它是np完全的。
. A run in a string is a nonextendable periodic substring in the string. Detecting all runs in a string is important and studied both from theoretical and practical points of view. In this paper, we consider the reverse problem of it. We reveal that the time complexity depends on the alphabet size k of the string to be output. We show that it is solvable in polynomial time for both binary alphabet and infinite alphabet, while it is NP-complete for finite k ≥ 4. We also consider a variant of the problem where only a subset of runs are given as an input. We show that it is solvable in polynomial time for infinite alphabet, while it is NP-complete for finite k ≥ 3.