Sliding suffix tree (Q2331636)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Sliding suffix tree |
scientific article |
Statements
Sliding suffix tree (English)
0 references
30 October 2019
0 references
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.
0 references
suffix tree
0 references
online pattern matching
0 references
sliding window
0 references
0 references