Verifying and enumerating parameterized border arrays

详细信息    查看全文

• 作者：Tomohiro  ; I^a ;   ; ^{tomohiro.i@inf.kyushu-u.ac.jp} ; Shunsuke  ; Inenaga  ; ;   ; ^a ;   ; ^{inenaga@inf.kyushu-u.ac.jp} ; Hideo  ; Bannai^a ;   ; ^{bannai@inf.kyushu-u.ac.jp} ; Masayuki  ; Takeda^a ;   ; ^{takeda@inf.kyushu-u.ac.jp}
• 关键词：String matching ; Parameterized pattern matching ; Reverse engineering ; Enumeration algorithms
• 刊名：Theoretical Computer Science
• 出版年：2011
• 出版时间：25 November 2011
• 年：2011
• 卷：412
• 期：50
• 页码：6959-6981
• 全文大小：621 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 a linear time algorithm to verify if a given integer array is a valid p-border array for a binary alphabet. We also show a linear time algorithm to compute all binary parameterized strings sharing a given p-border array. In addition, we give an algorithm which computes all p-border arrays of length at most , where is a given threshold. This algorithm runs in time, where is the number of all p-border arrays of length for a binary parameter alphabet.

The problems with a larger alphabet are much more difficult. Still, we present an ¨Ctime ¨Cspace algorithm to verify if a given integer array of length is a valid p-border array for an unbounded alphabet. The best previously known solution to this task takes time proportional to the -th Bell number , and hence our algorithm is much more efficient. Also, we show that it is possible to enumerate all p-border arrays of length at most for an unbounded alphabet in time, where denotes the number of p-border arrays of length .