first
prev
toc
next
last
Download Citation
Recommend
Mark
Alert
Link
Print
A HEURISTIC FOR COMPUTING REPEATS WITH A FACTOR ORACLE: APPLICATION TO BIOLOGICAL SEQUENCES
Authors:
Arnaud Lefebvre a;
Thierry Lecroq b
| Affiliations: | a ESA CNRS 6037-ABISS, Facult des Sciences, Universit de Rouen, 76821 Mont-Saint-Aignan Cedex, France. |
| b LIFAR-ABISS, Facult des Sciences, Universit de Rouen, 76821 Mont-Saint-Aignan Cedex, France. |
DOI:
10.1080/00207160214653
Publication Frequency:
12 issues per year
Published in:
International Journal of Computer Mathematics,
Volume
79,
Issue
12
2002
, pages 1303
- 1315
International Journal of Computer Mathematics,
Volume
79,
Issue
12
2002
, pages 1303
- 1315
Subjects:
Analysis - Mathematics;
Bioinformatics;
Computer Mathematics;
Discrete Mathematics;
Mathematical Finance;
Mathematical Logic;
Mathematical Numerical Analysis;
Systems & Computer Architecture;
Number of References: 16
Formats available:
PDF
(English)
Article Requests:
Order Reprints
:
Request Permissions
-
Single Article Purchase:
US$37.00
-
buy now
-
Sign In
- Online Sample
add to cart 
[ show other buying options ]
View Article:
View Article (PDF)
Abstract
We present in this article a linear time and space method for the computation of the length of a repeated suffix for each prefix of a given word p . Our method is based on the utilization of the factor oracle of p which is a new and very compact structure introduced in [1], used for representing all the factors of p . We exhibit applications where our method really speeds up the computation of repetitions in words.
|
| Keywords: Combinatorics On Word; String Algorithms; Repetitions; Factor Oracle; Suffix Link |
| view references (16) |
|
Bookmark with:
|
CiteULike
Del.icio.us
BibSonomy
Connotea
More bookmarks
