Data structures and algorithms for the string statistics problem |
| |
| Authors: | A. Apostolico F. P. Preparata |
| |
| Affiliation: | (1) Department of Computer Science, Purdue University, 47907 West Lafayette, IN, USA;(2) Dipartimento di Elettronica e Informatica, Università di Padova, Padova, Italy;(3) Department of Computer Science, Brown University, Providence, RI, USA |
| |
| Abstract: | Given a textstringx of lengthn, theMinimal Augmented Suffix Tree T (x) ofx is a digital-search index that returns, for anyquery stringw and in a number of comparisons bounded by the length ofw, the maximum number of nonoverlapping occurrences ofw inx. It is shown that, denoting the length ofx byn, T(x) can be built in timeO(n log2n) and spaceO(n logn), off-line on a RAM.This research was supported in part, through the Leonardo Fibonacci Institute, by the Istituto Trentino di Cultura, Trento, Italy.Additional support was provided by NSF Grants CCR-8900305 and CCR-9201078, by NATO Grant CRG 900293, by the National Research Council of Italy, and by the ESPRIT III Basic Research Programme of the EC under Contract No. 9072 (Project GEPPCOM).Additional support was provided by NSF Grant CCR-91-96176 and ONR Contract N 00014-91-J-4052, ARPA Order 2225. |
| |
| Keywords: | Design and analysis of algorithms Combinatorics on strings Pattern matching Substring statistics Suffix tree Augmented suffix tree Period of a string Repetition in a string |
| 本文献已被 SpringerLink 等数据库收录！ |
|
