A new approach to the periodicity lemma on strings with holes
MetadataShow full item record
We first give an elementary proof of the periodicity lemma for strings containing one hole (variously called a "wild card", a "don't-care" or an "indeterminate letter" in the literature). The proof is modelled on Euclid's algorithm for the greatest common divisor and is simpler than the original proof given in [J. Berstel, L. Boasson, Partial words and a theorem of Fine and Wilf, Theoret. Comput. Sci. 218 (1999) 135-141]. We then study the two-hole case, where our result agrees with the one given in [F. Blanchet-Sadri, Robert A. Hegstrom, Partial words and a theorem of Fine and Wilf revisited, Theoret. Comput. Sci. 270 (1-2) (2002) 401-419] but is more easily proved and enables us to identify a maximum-length prefix or suffix of the string to which the periodicity lemma does apply. Finally, we extend our result to three or more holes using elementary methods, and state a version of the periodicity lemma that applies to all strings with or without holes. We describe an algorithm that, given the locations of the holes in a string, computes maximum-length substrings to which the periodicity lemma applies, in time proportional to the number of holes. Our approach is quite different from that used by Blanchet-Sadri and Hegstrom, and also simpler.
The link to the journal’s home page is: http://www.elsevier.com/wps/find/journaldescription.cws_home/505625/description#description. Copyright © 2009 Elsevier B.V. All rights reserved
Showing items related by title, author, creator and subject.
Phillips, Bruce; Melville-Smith, R.; Thomson, A.; Rossbach, M. (2007)Previous studies have shown that western rock lobster pueruli and post-pueruli shelter in small holes and crevices and that suitable shelter in the inshore environment is limited. It is considered that by providing ...
Roufail, R.; Rasouli, Vamegh; Mokaramian, A.; Kamyab, Mohammadreza; Lagat, C.; Cavanough, G. (2013)Mineral exploration is in a race to employ drilling technology that can perform the exploration and drilling investigation in a fast and inexpensive manner. After an extensive study of the available drilling technologies ...
Crochemore, M.; Iliopoulos, Costas; Pissis, S.; Tischler, G. (2010)A proper fact or u of a string y is a cover of y if every letter of y is within some occurrence of u in y. The concept generalises the notion of periods of a string. An integer array C is the minimal-cover (resp. ...