.png){kind=icon}
.png){kind=icon}
Return
Sorting Circular Suffixes in Linear Time
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-01475-7_20.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In a well-studied variant of the dictionary matching problem, the strings in the dictionary are circular. Hon et al. [ISAAC 2011] showed how to solve circular dictionary queries efficiently within compressed space under some technical assumptions on the dictionary. Several papers studied the problem of building efficiently the required data structures, until Bannai et al. finally achieved linear time [CPM 2021] by presenting an algorithm for building the bijective Burrows-Wheeler transform. More precisely, to support circular dictionary matching queries efficiently, Hon et al. rely on Mantaci et al.'s eBWT, so Boucher et al. described a direct linear-time algorithm for building the eBWT [SPIRE 2021]. Very recently, it was shown how to solve circular dictionary queries in full generality by introducing a suffix array for arbitrary dictionaries [CPM 2025]. To build the suffix array and support circular dictionary queries, one needs to consider a problem more general than constructing the eBWT, because it is necessary to compute the ordered partition of all (infinite) suffixes with respect to the lexicographic order. In this paper, we provide a linear-time construction algorithm that extends Ko and Aluru's algorithm for building the suffix array. As a byproduct, we show that induced sorting yields a new linear-time algorithm to compute the primitive root of a string.
Keywords:
Circular dictionary matching
eBWT
induced sorting
dictionary matching
Burrows-Wheeler transform
Journal
D
IF:
0
Papers:
19
Citations:
0