King's College London

Research portal

Longest Repeats with a Block of Don't Cares

Research output: Chapter in Book/Report/Conference proceedingConference paper

Original languageEnglish
Title of host publicationLatin 2004
Subtitle of host publicationtheoretical informatics: 6th Latin American symposium, Buenos Aires, Argentina, April 5-8, 2004: proceedings
EditorsMartin Farach-Colton
Place of PublicationBERLIN
PublisherSpringer
Pages271-278
Number of pages8
VolumeN/A
EditionN/A
ISBN (Print)3540212582
Published2004
Event6th Latin American Symposium on Theoretical Informatics (LATIN 2004) - Buenos Aires, Argentina
Duration: 1 Jan 2004 → …

Publication series

NameLecture notes in computer science
PublisherSpringer
Volume2976

Conference

Conference6th Latin American Symposium on Theoretical Informatics (LATIN 2004)
CountryArgentina
CityBuenos Aires
Period1/01/2004 → …

King's Authors

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.

View graph of relations

© 2020 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454