Longest repeated motif with a block of don't cares

Maxime Crochemore 1, 2 Costas S. Iliopoulos 2 Manal Mohamed 2 Marie-France Sagot 3
1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 Department of Computer Science [London]
3 Baobab
PEGASE - Département PEGASE [LBBE]
Abstract : We introduce an algorithm for extracting all longest repeats with k don’t cares from a given sequence. Such repeats are composed of two parts separated by a block of k don’t care symbols. The algorithm uses suffix trees to fulfill this task and relies on the ability to answer the lowest common ancestor queries in constant time. It requires O(n log n) time in the worst-case.
Document type :
Conference papers
Complete list of metadatas
https://hal-upec-upem.archives-ouvertes.fr/hal-00619983
Contributor : Maxime Crochemore <>
Submitted on : Friday, December 18, 2015 - 9:32:47 AM
Last modification on : Thursday, November 21, 2019 - 1:14:05 PM
Long-term archiving on : Saturday, March 19, 2016 - 11:40:40 AM

File

LATIN2004.pdf
Files produced by the author(s)

Identifiers

Collections

UPEC-UPEM | CNRS | INRIA | BIOENVIS | LIGM | LIGM_ALGO | LIGM_MOA | ENPC | PARISTECH | UNIV-LYON1 | UDL

Citation

Maxime Crochemore, Costas S. Iliopoulos, Manal Mohamed, Marie-France Sagot. Longest repeated motif with a block of don't cares. 6th Latin American Theoretical Informatics (LATIN'04), 2004, Buenos Aires, Argentina. pp.271-278, ⟨10.1007/978-3-540-24698-5_31⟩. ⟨hal-00619983⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

404

Files downloads

127

Contact

CCSD