Sliding suffix tree (Q2331636)

Summary: We consider a sliding window \(W\) over a stream of characters from some alphabet of constant size. We want to look up a pattern in the current sliding window content and obtain all positions of the matches. We present an indexed version of the sliding window, based on a suffix tree. The data structure of size \(\Theta(|W|)\) has optimal time queries \(\Theta(m+\mathrm{occ})\) and amortized constant time updates, where \(m\) is the length of the query string and occ is its number of occurrences.