Verifying a Parameterized Border Array in O(n1.5) Time
Verifying a Parameterized Border Array in O(n1.5) Time
复制标题
DOI：
10.1007/978-3-642-13509-5_22
复制
发表时间：
2010-06
期刊：
影响因子：
--
通讯作者：
I. Tomohiro;Shunsuke Inenaga;H. Bannai;M. Takeda
中科院分区：
文献类型：
--
作者：
I. Tomohiro;Shunsuke Inenaga;H. Bannai;M. Takeda
参数化模式匹配问题是检验字母表上是否存在一个重命名的双射，通过这个双射，一个给定的模式可以被转换成一个给定文本的子串。参数化边界数组（p-border数组）是标准边界数组的参数化版本，使用p-border数组可以有效地解决参数化模式匹配问题。在本文中，我们提出了一个O（n1. 5)-时间复杂度为O（n）-空间算法，用于验证长度为n的给定整数数组是否是无界字母表的有效p边界数组。已知的最佳解所需的时间与第n个贝尔数1/e kn k= 0∞ kn/k！成正比，因此我们的算法是相当有效的。
The parameterized pattern matching problem is to check if there exists a renaming bijection on the alphabet with which a given pattern can be transformed into a substring of a given text. A parameterized border array (p-border array) is a parameterized version of a standard border array, and we can efficiently solve the parameterized pattern matching problem using p-border arrays. In this paper we present an O (n1. 5)-time O (n)-space algorithm to verify if a given integer array of length n is a valid p-border array for an unbounded alphabet. The best previously known solution takes time proportional to the n-th Bell number 1/eΣk= 0∞ kn/k!, and hence our algorithm is quite efficient.