2026-07-22T19:23:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20232 2024-07-02T07:52:53Z ddc:004 open_access

Breaking a Barrier in Constructing Compact Indexes for Parameterized Pattern Matching Iseri, Kento I, Tomohiro Hendrian, Diptarama Köppl, Dominik Yoshinaka, Ryo Shinohara, Ayumi Index for parameterized pattern matching Parameterized Burrows-Wheeler Transform Online construction A parameterized string (p-string) is a string over an alphabet (Σ_s ∪ Σ_p), where Σ_s and Σ_p are disjoint alphabets for static symbols (s-symbols) and for parameter symbols (p-symbols), respectively. Two p-strings x and y are said to parameterized match (p-match) if and only if x can be transformed into y by applying a bijection on Σ_p to every occurrence of p-symbols in x. The indexing problem for p-matching is to preprocess a p-string T of length n so that we can efficiently find the occurrences of substrings of T that p-match with a given pattern. Let σ_s and respectively σ_p be the numbers of distinct s-symbols and p-symbols that appear in T and σ = σ_s + σ_p. Extending the Burrows-Wheeler Transform (BWT) based index for exact string pattern matching, Ganguly et al. [SODA 2017] proposed parameterized BWTs (pBWTs) to design the first compact index for p-matching, and posed an open problem on how to construct the pBWT-based index in compact space, i.e., in O(n lg |Σ_s ∪ Σ_p|) bits of space. Hashimoto et al. [SPIRE 2022] showed how to construct the pBWT for T, under the assumption that Σ_s ∪ Σ_p = [0..O(σ)], in O(n lg σ) bits of space and O(n (σ_p lg n)/(lg lg n)) time in an online manner while reading the symbols of T from right to left. In this paper, we refine Hashimoto et al.’s algorithm to work in O(n lg σ) bits of space and O(n (lg σ_p lg n)/(lg lg n)) time in a more general assumption that Σ_s ∪ Σ_p = [0..n^{O(1)}]. Our result has an immediate application to constructing parameterized suffix arrays in O(n (lg σ_p lg n)/(lg lg n)) time and O(n lg σ) bits of working space. We also show that our data structure can support backward search, a core procedure of BWT-based indexes, at any stage of the online construction, making it the first compact index for p-matching that can be constructed in compact space and even in an online manner. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kento Iseri and Tomohiro I and Diptarama Hendrian and Dominik Köppl and Ryo Yoshinaka and Ayumi Shinohara 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.89 urn:nbn:de:0030-drops-202324 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.89 eng https://creativecommons.org/licenses/by/4.0/legalcode