Efficient seed computation revisited

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(n log(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) [14].
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2013, 483, pp.171 - 181. 〈10.1016/j.tcs.2011.12.078〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal-upec-upem.archives-ouvertes.fr/hal-01616469
Contributeur : Maxime Crochemore <>
Soumis le : vendredi 13 octobre 2017 - 16:45:34
Dernière modification le : jeudi 17 mai 2018 - 12:52:03

Fichier

seeds.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Citation

M. Christou, Maxime Crochemore, C.S. Iliopoulos, M. Kubica, S.P. Pissis, et al.. Efficient seed computation revisited. Theoretical Computer Science, Elsevier, 2013, 483, pp.171 - 181. 〈10.1016/j.tcs.2011.12.078〉. 〈hal-01616469〉

Partager

Métriques

Consultations de la notice

52

Téléchargements de fichiers

14