Search
Close this search box.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

  • Research article

On the Appearance of Seeds In Words

Manolis Christodoulakis1, Michalis Christou2, Maxime Crochemore3, Costas 8S. [liopoulos4
1Department of Electrical and Computer Engineering, University of Cyprus, P.O. Box 20537, 1678 Nicosia, Cyprus
2Department of Informatics, King’s College London, Strand, London WC2R 2LS, UK
3Department of Informatics, King’s College London, Strand, London WC2R 2LS, UK Université Paris-Est, France
4Department of Informatics, King’s College London, Strand, London WC2R 2LS, UK Curtin University, Digital Ecosystems & Business Intelligence Institute, Center for stringology & Applications, Australia
  • Published: 30/11/2015

Abstract

A seed of a word \( x \) is a cover of a superword of \( x \). In this paper, we study the frequency of appearance of seeds in words. We give bounds for the average number of seeds in a word and we investigate the maximum number of distinct seeds that can appear in a word. More precisely, we prove that a word has \( O(n) \) seeds on average and that the maximum number of distinct seeds in a word is between \( \frac{1}{6}(n^2) + o(n^2) \) and \( \frac{1}{4}(n^2) + o(n^2) \), and we reveal some properties of an extremal word for the last case.

Information
Guidelines
CP Initiatives
Follow CP
Facebook Twitter Linkedin
1970-2024 CP (Manitoba, Canada) unless otherwise stated.
Citation
Manolis Christodoulakis, Michalis Christou, Maxime Crochemore, Costas 8S. [liopoulos. On the Appearance of Seeds In Words[J], Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 095. 147-160. DOI: .