Optimal-Time Contextual Pattern Matching in Compressed Space

Gonzalo Navarro and Francisco Olivares

Contextual pattern matching is the task of, given a pattern P[1,m], a context length l, and a text T[1,n], find all the occ distinct contexts in which P occurs in T, the context being the l symbols preceding and the l symbols following the occurrence; a text position where each context occurs must be output. While the problem can be solved in optimal time O(m+occ) using O(n)-space precomputed data structures on T, this type of search is particularly relevant on large repetitive text collections, where O(n) space can be prohibitive. We present the first optimal-time solution that runs in compressed space, namely that of a symmetric CDAWG (SCDAWG) of T. Further, we show how the set of occ solutions can be enumerated with O(log log l) delay after O(m)-time preprocessing of P. To achieve this, we develop an improved linear-space distance-sensitive weighted ancestor data structure.