2026-07-23T06:52:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8256 2024-03-06T10:41:50Z ddc:004 open_access

Structural Pattern Matching - Succinctly Ganguly, Arnab Shah, Rahul Thankachan, Sharma V. Parameterized Pattern Matching Suffix tree Burrows-Wheeler Transform Wavelet Tree Fully-functional succinct tree Let T be a text of length n containing characters from an alphabet \Sigma, which is the union of two disjoint sets: \Sigma_s containing static characters (s-characters) and \Sigma_p containing parameterized characters (p-characters). Each character in \Sigma_p has an associated complementary character from \Sigma_p. A pattern P (also over \Sigma) matches an equal-length substring $S$ of T iff the s-characters match exactly, there exists a one-to-one function that renames the p-characters in S to the p-characters in P, and if a p-character x is renamed to another p-character y then the complement of x is renamed to the complement of y. The task is to find the starting positions (occurrences) of all such substrings S. Previous indexing solution [Shibuya, SWAT 2000], known as Structural Suffix Tree, requires \Theta(n\log n) bits of space, and can find all occ occurrences in time O(|P|\log \sigma+ occ), where \sigma = |\Sigma|. In this paper, we present the first succinct index for this problem, which occupies n \log \sigma + O(n) bits and offers O(|P|\log\sigma+ occ\cdot \log n \log\sigma) query time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arnab Ganguly and Rahul Shah and Sharma V. Thankachan 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.35 urn:nbn:de:0030-drops-82566 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.35 eng https://creativecommons.org/licenses/by/3.0/legalcode