Opening book details…
Can I read Parameterized Pattern Matching -- Succinctly on EtoBox?
Parameterized Pattern Matching -- Succinctly by Ganguly, Arnab; Shah, Rahul; Thankachan, Sharma V. is a scholarly article available to read on EtoBox.
What is Parameterized Pattern Matching -- Succinctly about?
We consider the $Parameterized$ $Pattern$ $Matching$ problem, where a pattern $P$ matches some location in a text $\mathsf{T}$ iff there is a one-to-one correspondence between the alphabet symbols of the pattern to those of the text. More specifically, assume that the text $\mathsf{T}$ contains $n$ characters from a static alphabet $\Sigma_s$ and a parameterized alphabet $\Sigma_p$, where $\Sigma_s \cap \Sigma_p = \varnothing$ and $|\Sigma_s \cup \Sigma_p|=\sigma$. A pattern $P$ matches a substring $S$ of $\mathsf{T}$ iff the static characters match exactly, and there exists a one-to-one function that renames the parameterized characters in $S$ to that in $P$. Previous indexing solution [Baker, STOC 1993], known as $Parameterized$ $Suffix$ $Tree$, requires $\Theta(n\log n)$ bits of space, and can find all $occ$ occurrences of $P$ in $\mathcal{O}(|P|\log \sigma+ occ)$ time. In this paper, we present the first succinct index that occupies $n \log \sigma + \mathcal{O}(n)$ bits and answers queries in $\mathcal{O}((|P|+ occ\cdot \log n) \log\sigma\log \log \sigma)$ time. We also present a compact index that occupies $\mathcal{O}(n\log\sigma)$ bits and answers queries in $\mathcal{O}(|P|
- Author
- Ganguly, Arnab; Shah, Rahul; Thankachan, Sharma V.
- Published
- 2016
- Language
- EN
More by Ganguly, Arnab; Shah, Rahul; Thankachan, Sharma V.
Browse all works by Ganguly, Arnab; Shah, Rahul; Thankachan, Sharma V.