The Parameterized Suffix Tray

Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

研究成果: 書籍/レポート タイプへの寄稿会議への寄与

2 被引用数 (Scopus)


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.

ホスト出版物のタイトルAlgorithms and Complexity - 12th International Conference, CIAC 2021, Proceedings
編集者Tiziana Calamoneri, Federico Corò
出版社Springer Science and Business Media Deutschland GmbH
出版ステータス出版済み - 2021
イベント12th International Conference on Algorithms and Complexity, CIAC 2021 - Virtual, Online
継続期間: 5月 10 20215月 12 2021


名前Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
12701 LNCS


会議12th International Conference on Algorithms and Complexity, CIAC 2021
CityVirtual, Online

!!!All Science Journal Classification (ASJC) codes

  • 理論的コンピュータサイエンス
  • コンピュータ サイエンス(全般)


「The Parameterized Suffix Tray」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。