论文标题
语法压缩字符串中的节奏
Cadences in Grammar-Compressed Strings
论文作者
论文摘要
节奏在结构上是与基础字符串中相等字符相对应的指数的最大算术进程。 本文为语法压缩的二进制字符串提供了三个循环的多项式时间检测算法。该算法还可以转化为未压缩二进制字符串中3个填充的线性时间检测算法。 此外，本文证明了节奏检测问题的几种变体对于语法压缩字符串而言是NP的完整。结果，对于语法压缩的三元字符串而言，等距的子序列匹配问题与长度三的模式是NP完整的。
Cadences are structurally maximal arithmetic progressions of indices corresponding to equal characters in an underlying string. This paper provides a polynomial time detection algorithm for 3-cadences in grammar-compressed binary strings. This algorithm also translates to a linear time detection algorithm for 3-cadences in uncompressed binary strings. Furthermore, this paper proves that several variants of the cadence detection problem are NP-complete for grammar-compressed strings. As a consequence, the equidistant subsequence matching problem with patterns of length three is NP-complete for grammar-compressed ternary strings.
