Abstract
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 Σ of cardinality σ. 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 ∈ P that is a p-match with the substring T[j, j + |P i | - 1]. ▪ insert(P i )/delete(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) insert(P i ) and delete(P i ) in amortized O(|P i | polylog(n)) time. Then, we present a succinct index that occupies (1+o(1))n log σ+O(d log n) bits and supports (i) search(T) in worst-case O(|T| log 2 n+occ) time, and (ii) insert(P i ) and delete(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.