Pattern-Matching for Strings with Short Descriptions
Pattern-Matching for Strings with Short Descriptions
复制标题
具有简短描述的字符串的模式匹配
DOI：
10.1007/3-540-60044-2_44
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
A. Shinohara
中科院分区：
文献类型：
--
作者：
Marek Karpinski;W. Rytter;A. Shinohara
我们考虑被简洁描述的字符串。描述是用直线程序的形式进行的，其中常量是符号，唯一的操作是连接。这样的描述对应于递归系统或与上下文无关的生成单个单词的语法。字符串的描述性大小是定义该字符串的直线程序（或语法的大小）的长度。通常描述大小的字符串是指数长度。斐波那契和莫尔斯字就是这种字符串的例子。我们证明，对于描述大小为n的pattern（）和text()，可以在关于ton的时间多项式中找到（如果有的话）pintt的出现。这是非常重要的，因为pandt的实际长度可能是指数级的，并且没有任何已知的字符串匹配算法可以直接应用。我们的第一个工具是周期性引理，它允许用可行的许多等差数列来表示一些指数多位置的集合。第二个工具是算术：欧几里得算法的一个简单应用。因此，对于指数级长字符串的文本问题在这里被简化为具有（仅）线性多位的整数的简单算术。我们还提出了一个np完全版本的模式匹配的简短描述字符串。
We consider strings which are succinctly described. The description is in terms of straight-line programs in which the constants are symbols and the only operation is the concatenation. Such descriptions correspond to the systems of recurrences or to context-free grammars generating single words. The descriptive size of a string is the lengthnof a straight-line program (or size of a grammar) which defines this string. Usually the strings of descriptive sizenare of exponential length.FibonacciandThue-Morse wordsare examples of such strings. We show that for a patternPand textTof descriptive sizesm, n, an occurrence ofPinTcan be found (if there is any) in time polynomial with respect ton. This is nontrivial, since the actual lengths ofPandTcould be exponential, and none of the known string-matching algorithms is directly applicable. Our first tool is the periodicity lemma, which allows to represent some sets of exponentially many positions in terms of feasibly many arithmetic progressions. The second tool is arithmetics: a simple application of Euclid algorithm. Hence a textual problem for exponentially long strings is reduced here to simple arithmetics on integers with (only) linearly many bits. We present also an NP-complete version of the pattern-matching for shortly described strings.