Conference
THE STRUCTURE OF FACTOR ORACLES
Abstract
The factor oracle is a relatively new data structure for the set of factors of a string. It has been introduced by Allauzen, Crochemore, and Raffinot in 1999. It may recognize non-factors (hence the name "oracle") but its implementational simplicity and experimental behaviour are stunning; factor oracle based string matching has been conjectured optimal on average. However, its structure is not well understood. We take important steps in …
Authors
CROCHEMORE M; ILIE L; SEID-HILMI E
Volume
18
Pagination
pp. 781-797
Publisher
World Scientific Publishing
Publication Date
August 2007
DOI
10.1142/s0129054107004978
Conference proceedings
International Journal of Foundations of Computer Science
Issue
04
ISSN
0129-0541