Prague Stringology Conference 2026
Laurentius Leonard, Shunsuke Inenaga, Hideo Bannai and Takuya Mieno
Sliding Suffix Trees Revisited
| Abstract: |
|
The sliding suffix tree (Fiala&Greene, 1989) is a suffix tree
that is maintained for a sliding window Wi=T[i..i+d-1] of size d
that shifts over an input text T of length n from left to right, for increasing i = 1, ..., n-d+1.
It is known that the sliding suffix tree can be maintained in O(n log σ) time with O(d) space, where
σ is the alphabet size.
Updating the sliding suffix tree from Wi=T[i..i+d-1] to Wi+1=T[i+1..i+d]
requires the following three major tasks: (1) Delete the leaf that represents the longest suffix Wi, (2) Insert new leaves that represent the suffixes of Wi+1 that appear exactly once in Wi+1, and (3) After the leaf deletion due to Task (1) and each leaf insertion due to Task (2), maintain the label 〈l, r〉 of every edge as a valid pair in the new window Wi+1, such that i+1 ≤ l ≤ r ≤ i+d. In this paper, we present the first algorithm that performs Task (3) in O(1) worst-case time per node deletion/insertion, which leads to another alternative to efficient sliding suffix tree construction. This is an improvement over the existing algorithms by Larsson (1996, 1999) and by Senft (2005) both of which can only perform Task (3) in O(1) amortized time. Our key data structure is a non-trivial extension of leaf pointers, which were originally proposed by Brodnik and Jekovec (2018) for pattern matching with sliding suffix trees. |
| Download paper: |  |
 |
|
| BibTeX reference |