TY - GEN

T1 - Verifying a parameterized border array in O(n1.5) time

AU - I, Tomohiro

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Takeda, Masayuki

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=78449275272&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78449275272&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-13509-5_22

DO - 10.1007/978-3-642-13509-5_22

M3 - Conference contribution

AN - SCOPUS:78449275272

SN - 3642135080

SN - 9783642135088

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 238

EP - 250

BT - Combinatorial Pattern Matching - 21st Annual Symposium, CPM 2010, Proceedings

PB - Springer Verlag

ER -