TY - GEN
T1 - The Parameterized Suffix Tray
AU - Fujisato, Noriki
AU - Nakashima, Yuto
AU - Inenaga, Shunsuke
AU - Bannai, Hideo
AU - Takeda, Masayuki
N1 - Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - Let Σ and Π be disjoint alphabets, respectively called the static alphabet and the parameterized alphabet. Two strings x and y over Σ∪ Π of equal length are said to parameterized match (p-match) if there exists a renaming bijection f on Σ and Π which is identity on Σ and maps the characters of x to those of y so that the two strings become identical. The indexing version of the problem of finding p-matching occurrences of a given pattern in the text is a well-studied topic in string matching. In this paper, we present a state-of-the-art indexing structure for p-matching called the parameterized suffix tray of an input text T, denoted by PSTray(T). We show that PSTray(T) occupies O(n) space and supports pattern matching queries in O(m+ log (σ+ π) + occ) time, where n is the length of t, m is the length of a query pattern P, π is the number of distinct symbols of | Π| in T, σ is the number of distinct symbols of | Σ| in T and occ is the number of p-matching occurrences of P in T. We also present how to build PSTray(T) in O(n) time from the parameterized suffix tree of T.
AB - Let Σ and Π be disjoint alphabets, respectively called the static alphabet and the parameterized alphabet. Two strings x and y over Σ∪ Π of equal length are said to parameterized match (p-match) if there exists a renaming bijection f on Σ and Π which is identity on Σ and maps the characters of x to those of y so that the two strings become identical. The indexing version of the problem of finding p-matching occurrences of a given pattern in the text is a well-studied topic in string matching. In this paper, we present a state-of-the-art indexing structure for p-matching called the parameterized suffix tray of an input text T, denoted by PSTray(T). We show that PSTray(T) occupies O(n) space and supports pattern matching queries in O(m+ log (σ+ π) + occ) time, where n is the length of t, m is the length of a query pattern P, π is the number of distinct symbols of | Π| in T, σ is the number of distinct symbols of | Σ| in T and occ is the number of p-matching occurrences of P in T. We also present how to build PSTray(T) in O(n) time from the parameterized suffix tree of T.
UR - http://www.scopus.com/inward/record.url?scp=85106165456&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85106165456&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-75242-2_18
DO - 10.1007/978-3-030-75242-2_18
M3 - Conference contribution
AN - SCOPUS:85106165456
SN - 9783030752415
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 258
EP - 270
BT - Algorithms and Complexity - 12th International Conference, CIAC 2021, Proceedings
A2 - Calamoneri, Tiziana
A2 - Corò, Federico
PB - Springer Science and Business Media Deutschland GmbH
T2 - 12th International Conference on Algorithms and Complexity, CIAC 2021
Y2 - 10 May 2021 through 12 May 2021
ER -