Sliding Suffix Tree using LCA

Author
Abstract
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.
Year of Publication
2018
Document Number
LUSY-2018/01
Number of Pages
9
Date Published
01/2018
Type
Report
Institution
University of Ljubljana, Faculty of Computer and Information Science
City
Ljubljana
Report Number
LUSY-2018/01
URL
https://arxiv.org/abs/1801.07449
The website encountered an unexpected error. Please try again later.
Error: Call to undefined method stdClass::getPathname() in _system_rebuild_module_data() (line 1042 of core/modules/system/system.module).