2026-07-21T03:18:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6025 2024-03-06T10:37:29Z ddc:004 open_access

A Framework for Dynamic Parameterized Dictionary Matching Ganguly, Arnab Hon, Wing-Kai Shah, Rahul Parameterized Dictionary Indexing Generalized Suffix Tree Succinct Data Structures Sparsification Two equal-length strings S and S' are a parameterized-match (p-match) iff there exists a one-to-one function that renames the characters in S to those in S'. Let P be a collection of d patterns of total length n characters that are chosen from an alphabet Sigma of cardinality sigma. The task is to index P such that we can support the following operations. * search(T): given a text T, report all occurrences <j,P_i> such that there exists a pattern P_i in P that is a p-match with the substring T[j,j+|P_i|-1]. * ins(P_i)/del(P_i): modify the index when a pattern P_i is inserted/deleted. We present a linear-space index that occupies O(n*log n) bits and supports (i) search(T) in worst-case O(|T|*log^2 n + occ) time, where occ is the number of occurrences reported, and (ii) ins(P_i) and del(P_i) in amortized O(|P_i|*polylog(n)) time. Then, we present a succinct index that occupies (1+o(1))n*log sigma + O(d*log n) bits and supports (i) search(T) in worst-case O(|T|*log^2 n + occ) time, and (ii) ins(P_i) and del(P_i) in amortized O(|P_i|*polylog(n)) time. We also present results related to the semi-dynamic variant of the problem, where deletion is not allowed. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arnab Ganguly and Wing-Kai Hon and Rahul Shah 2016 Is Part Of LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2016.10 urn:nbn:de:0030-drops-60256 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.10 eng https://creativecommons.org/licenses/by/3.0/legalcode