TY - RPRT
AU - Andrej Brodnik
AU - Matevž Jekovec
AB - We consider a sliding window W over a stream of characters from some alphabet of constant size. The user wants to perform deterministic substring matching on the current sliding window content and obtain positions of the matches. We present an indexed version of the sliding window using the suffix tree, the link tree and the lowest common ancestor. The data structure of size Θ(|W|) has optimal time queries Θ(m+occ) and amortized constant time updates, where m is the length of the query string and occ is the number of its occurrences. 
CY - Ljubljana
M1 - LUSY-2018/01
M3 - Report
N2 - We consider a sliding window W over a stream of characters from some alphabet of constant size. The user wants to perform deterministic substring matching on the current sliding window content and obtain positions of the matches. We present an indexed version of the sliding window using the suffix tree, the link tree and the lowest common ancestor. The data structure of size Θ(|W|) has optimal time queries Θ(m+occ) and amortized constant time updates, where m is the length of the query string and occ is the number of its occurrences. 
PB - University of Ljubljana, Faculty of Computer and Information Science
PY - 2018
EP - 9
TI - Sliding Suffix Tree using LCA
UR - https://arxiv.org/abs/1801.07449
SN - LUSY-2018/01
ER -