{"ID":5438566,"CreatedAt":"2026-07-01T01:17:58.482524686Z","UpdatedAt":"2026-07-03T01:40:09.565152011Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.31030","arxiv_id":"2606.31030","title":"Optimal-Time Contextual Pattern Matching in Compressed Space","abstract":"Contextual pattern matching is the task of, given a pattern $P[1,m]$, a context length $λ$, and a text $T[1,n]$, find all the $occ$ distinct contexts in which $P$ occurs in $T$, the context being the $λ$ symbols preceding and the $λ$ 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λ)$ delay after $O(m)$-time preprocessing of $P$. To achieve this, we develop an improved linear-space distance-sensitive weighted ancestor data structure.","short_abstract":"Contextual pattern matching is the task of, given a pattern $P[1,m]$, a context length $λ$, and a text $T[1,n]$, find all the $occ$ distinct contexts in which $P$ occurs in $T$, the context being the $λ$ symbols preceding and the $λ$ symbols following the occurrence; a text position where each context occurs must be ou...","url_abs":"https://arxiv.org/abs/2606.31030","url_pdf":"https://arxiv.org/pdf/2606.31030v1","authors":"[\"Gonzalo Navarro\",\"Francisco Olivares\"]","published":"2026-06-30T01:56:53Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}