King's College London

Research portal

Longest repeats with a block of k don't cares

Research output: Contribution to journalArticle

Original languageEnglish
Pages (from-to)248-254
Number of pages7
JournalJournal of Theoretical Computer Science
Volume362
Issue number1-3
DOIs
Published11 Oct 2006

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

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