DATA-STRUCTURES AND ALGORITHMS FOR THE STRING STATISTICS PROBLEM

Authors
APOSTOLICO A PREPARATA FP
Citation
A. Apostolico et Fp. Preparata, DATA-STRUCTURES AND ALGORITHMS FOR THE STRING STATISTICS PROBLEM, Algorithmica, 15(5), 1996, pp. 481-494
Citations number
7
Categorie Soggetti
Computer Sciences",Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Algorithmica → ACNP
ISSN journal
01784617
Volume
15
Issue
5
Year of publication
1996
Pages
481 - 494
Database
ISI
SICI code
0178-4617(1996)15:5<481:DAAFTS>2.0.ZU;2-S
Abstract
Given a textstring x of length n, the Minimal Augmented Suffix Tree (T ) over cap (x) of x is a digital-search index that returns, for any qu ery string w and in a number of comparisons bounded by the length of w , the maximum number of nonoverlapping occurrences of w in x. It is sh own that, denoting the length of x by n, (T) over cap (x) can be built in time O(n log(2) n) and space O(n log n), off-line on a RAM.