TY - GEN
T1 - Counting parameterized border arrays for a binary alphabet
AU - I, Tomohiro
AU - Inenaga, Shunsuke
AU - Bannai, Hideo
AU - Takeda, Masayuki
PY - 2009/1/1
Y1 - 2009/1/1
N2 - The parameterized pattern matching problem is a kind of pattern matching problem, where a pattern is considered to occur in a text when there exists a renaming bijection on the alphabet with which the pattern can be transformed into a substring of the text. A parameterized border array (p-border array) is an analogue of a border array of a standard string, which is also known as the failure function of the Morris-Pratt pattern matching algorithm. 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 n, where n is a a given threshold. This algorithm runs in time linear in the number of output p-border arrays.
AB - The parameterized pattern matching problem is a kind of pattern matching problem, where a pattern is considered to occur in a text when there exists a renaming bijection on the alphabet with which the pattern can be transformed into a substring of the text. A parameterized border array (p-border array) is an analogue of a border array of a standard string, which is also known as the failure function of the Morris-Pratt pattern matching algorithm. 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 n, where n is a a given threshold. This algorithm runs in time linear in the number of output p-border arrays.
UR - http://www.scopus.com/inward/record.url?scp=67649999065&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=67649999065&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-00982-2_36
DO - 10.1007/978-3-642-00982-2_36
M3 - Conference contribution
AN - SCOPUS:67649999065
SN - 9783642009815
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 422
EP - 433
BT - Language and Automata Theory and Applications - Third International Conference, LATA 2009, Proceedings
PB - Springer Verlag
T2 - 3rd International Conference on Language and Automata Theory and Applications, LATA 2009
Y2 - 2 April 2009 through 8 April 2009
ER -