Periods in strings. (English) Zbl 0464.68070


68R99 Discrete mathematics in relation to computer science


string matching
Full Text: DOI


[1] Boyer, S.B; Moore, J.S, A fast string searching algorithm, Comm. assoc. comput. Mach., 20, 762-771, (1977) · Zbl 1219.68165
[2] Fine, N.J; Wilf, H.S, Uniqueness theorems for periodic functions, (), 109-114 · Zbl 0131.30203
[3] Gardner, M, On the paradoxical situations that arise from nontransitive relations, Sci. amer., 120-125, (October 1974)
[4] Guibas, L.J; Odlyzko, A.M, A new proof of the linearity of the boyer-Moore string searching algorithm, (), Revised version SIAM J. Comput., in press · Zbl 0446.68050
[5] {\scL. J. Guibas and A. M. Odlyzko}, String overlaps, pattern matching, and nontransitive games, J. Combinatorial Theory Ser. A, in press. · Zbl 0454.68109
[6] Galil, Z; Seiferas, J, Saving space in fast string matching, () · Zbl 0446.68041
[7] Harborth, H, Endliche 0-1-folgen mit gleichen teilblöcken, Crelle’s J., 271, 139-154, (1974) · Zbl 0297.05008
[8] Knuth, D.E; Morris, J.H; Pratt, V.R, Fast pattern matching in strings, SIAM J. comput., 6, 323-350, (1977) · Zbl 0372.68005
[9] Lyndon, R.C; Schützenberger, M.P, The equation aM = bncp in a free group, Michigan math. J., 9, 289-298, (1962) · Zbl 0106.02204
[10] Nielsen, T.P, On the expected duration of a search for a fixed pattern in random data, IEEE trans. inform theory, 702-704, (1973) · Zbl 0278.94008
[11] Schützenberger, M.P, A property of finitely generated submonoids of free monoids, (), in press · Zbl 0413.20042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.