@article{abedin_chubet_gibney_thankachan_2023, title={Contextual Pattern Matching in Less Space}, ISSN={["1068-0314"]}, DOI={10.1109/DCC55655.2023.00024}, abstractNote={We revisit the Contextual Pattern Matching Problem, defined as follows: preprocess a text T[1, n], so that given a query consisting of a string P and a length P, the occurrences of all distinct strings XPY where |X|=|Y|=P can be reported. This problem was introduced by Navarro, who presented an O($\overline{r}\log(n/\overline{r}))$ space data structure, where $\overline{r}$ is the maximum of the number of runs in the BWT of the text $\mathrm{T}[1,n]$ and its reverse. His solution reports all c contextual occurrences in $O(|P|+c\log n)$ time. However, the only known bounds on $\overline{r}$ are $\overline{r}=O(r\log^{2}n)$ where r is the number of runs in the BWT of T, making it desirable to avoid using structures with space dependent on $\overline{r}$. We demonstrate that this is possible without a significant sacrifice in query time by providing an $O(r\log(n/r))$ space solution that answers queries in $O(|P|+c\log P\cdot\log(n/r))$ time.}, journal={2023 DATA COMPRESSION CONFERENCE, DCC}, author={Abedin, Paniz and Chubet, Oliver and Gibney, Daniel and Thankachan, Sharma V.}, year={2023}, pages={160–167} }