An Improved Pattern Matching Algorithm for Strings in Terms of Straight-Line Programs
An Improved Pattern Matching Algorithm for Strings in Terms of Straight-Line Programs
复制标题
一种改进的直线规划字符串模式匹配算法
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
M. Takeda
中科院分区：
文献类型：
--
作者：
Masamichi Miyazaki;A. Shinohara;M. Takeda
我们展示了一种高效的字符串模式匹配算法，该算法用直线程序简洁地描述，其中常量是符号，唯一的操作是连接。在本文中，文本T和模式P都由直线程序T和P给出。文本T（模式P，等）的长度可以相对于其描述大小‖T‖=n（‖P‖=m，等）呈指数增长。我们展示了一个关于文本中模式周期性出现的新的组合属性。基于这一性质，我们开发了一种使用O（nm）空间的O（n2m2）时间算法，该算法输出t中所有P出现的紧凑表示。这优于Karpinski等人提出的算法，该算法使用O（(n+m)3）空间在O(（n+m)4 log (n+m)）时间内运行，并且只发现一次出现。此外，我们的算法比他们的简单得多。
We show an efficient pattern-matching algorithm for strings that are succinctly described in terms of straight-line programs, in which the constants are symbols and the only operation is the concatenation. In this paper, both text T and pattern P are given by straight-line programs T and P. The length of the text T (pattern P, resp.) may grow exponentially with respect to its description size ‖T‖=n (‖p‖=m, resp.). We show a new combinatorial property concerning with the periodic occurrences of a pattern in a text. Based on this property, we develop an O(n2m2) time algorithm using O(nm) space, which outputs a compact representation of all occurrences of P in T. This is superior to the algorithm proposed by Karpinski et al. [11], which runs in O((n+m)4 log (n+m)) time using O((n+m)3) space, and finds only one occurrence. Moreover, our algorithm is much simpler than theirs.