STRING OVERLAPS, PATTERN-MATCHING, AND NON-TRANSITIVE GAMES
STRING OVERLAPS, PATTERN-MATCHING, AND NON-TRANSITIVE GAMES
复制标题
DOI：
10.1016/0097-3165(81)90005-4
复制
发表时间：
1981-01-01
影响因子：
1.1
通讯作者：
ODLYZKO, AM
中科院分区：
文献类型：
--
作者：
GUIBAS, LJ;ODLYZKO, AM
本文研究了有关字符串重叠方式的几个主题。引入了两个字符串的对应关系的关键概念，它是第二个字符串如何重叠到第一个字符串的表示。然后，这个概念被用来陈述和证明一个生成函数的公式，该生成函数枚举长度为q的字符串，这些字符串不包含给定的有限模式集。文中还讨论了这一基本结果的各种推广。这个公式接下来被用来研究各种各样看似无关的问题。第一个应用是关于概率掷硬币博弈中的非传递优势关系。另一个应用表明，在最坏的情况下，如果不检查文本的基本上所有字符，没有任何算法可以检查文本中给定模式的存在。最后，证明了与主要结果相关的一类多项式是不可约的。
This paper studies several topics concerning the way strings can overlap. The key notion of thecorrelationof two strings is introduced, which is a representation of how the second string can overlap into the first. This notion is then used to state and prove a formula for the generating function that enumerates theq-ary strings of lengthnwhich contain none of a given finite set of patterns. Various generalizations of this basic result are also discussed. This formula is next used to study a wide variety of seemingly unrelated problems. The first application is to the nontransitive dominance relations arising out of a probabilistic coin-tossing game. Another application shows that no algorithm can check for the presence of a given pattern in a text without examining essentially all characters of the text in the worst case. Finally, a class of polynomials arising in connection with the main result are shown to be irreducible.