# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Fast Lightweight Suffix Array Construction and Checking

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Burkhardt, S., & Kärkkäinen, J. (2003). Fast Lightweight Suffix Array Construction
and Checking. In *Combinatorial Pattern Matching: 14th Annual Symposium, CPM 2003* (pp. 55-69).
Heidelberg, Germany: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-2D03-F

##### Abstract

We describe an algorithm that, for any $v\in[2,n]$, constructs
the suffix array of a string of length $n$ in $\Oh{vn + n \log
n}$ time using $\Oh{v+n/\sqrt{v}}$ space in addition to the
input (the string) and the output (the suffix array). By setting
$v=\log n$, we obtain an $\Oh{n \log n}$ time algorithm using
$\Oh{n/\sqrt{\log n}}$ extra space. This solves the open problem
stated by Manzini and Ferragina [ESA\;'02] of whether there
exists a lightweight (sublinear extra space) $\Oh{n \log n}$ time
algorithm. The key idea of the algorithm is to first sort a
sample of suffixes chosen using mathematical constructs called
difference covers. The algorithm is not only lightweight but also
fast in practice as demonstrated by experiments. Additionally,
we describe fast and lightweight suffix array checkers, i.e.,
algorithms that check the correctness of a suffix array.