Efficient seeds computation revisited

Michalis Christou*, Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Bartosz Szreder, Tomasz Waleń

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

The notion of the cover is a generalization of a period of a string, and there are linear time algorithms for finding the shortest cover. The seed is a more complicated generalization of periodicity, it is a cover of a superstring of a given string, and the shortest seed problem is of much higher algorithmic difficulty. The problem is not well understood, no linear time algorithm is known. In the paper we give linear time algorithms for some of its versions - computing shortest left-seed array, longest left-seed array and checking for seeds of a given length. The algorithm for the last problem is used to compute the seed array of a string (i.e., the shortest seeds for all the prefixes of the string) in O(n 2) time. We describe also a simpler alternative algorithm computing efficiently the shortest seeds. As a by-product we obtain an O(nlog(n/m)) time algorithm checking if the shortest seed has length at least m and finding the corresponding seed. We also correct some important details missing in the previously known shortest-seed algorithm (Iliopoulos et al., 1996).

Original languageEnglish
Title of host publicationCombinatorial Pattern Matching - 22nd Annual Symposium, CPM 2011, Proceedings
Pages350-363
Number of pages14
DOIs
Publication statusPublished - 13 Jul 2011
Externally publishedYes
Event22nd Annual Symposium on Combinatorial Pattern Matching, CPM 2011 - Palermo, Italy
Duration: 27 Jun 201129 Jun 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6661 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference22nd Annual Symposium on Combinatorial Pattern Matching, CPM 2011
CountryItaly
CityPalermo
Period27/06/1129/06/11

Fingerprint

Dive into the research topics of 'Efficient seeds computation revisited'. Together they form a unique fingerprint.

Cite this