×

zbMATH — the first resource for mathematics

Optimal off-line detection of repetitions in a string. (English) Zbl 0497.68052

MSC:
68T99 Artificial intelligence
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aho, A.V.; Hoperoft, J.F.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, MA
[2] Apostolico, A., Fast applications of suffix trees, (), 558-567
[3] Braunholtz, C.H., Solution to problem 5030, Ann. of math., 70, 675-676, (1963)
[4] Crochemore, M., An optimal algorithm for computing the repetitions in a word, Information processing lett., 12, 5, 244-250, (1981) · Zbl 0467.68075
[5] Duval, J.P., Sur la périodicité des mots, () · Zbl 0482.68078
[6] Fine, N.J.; Wilf, H.S., Uniqueness theorems for periodic functions, Proc. amer. math. soc., 16, 109-114, (1965) · Zbl 0131.30203
[7] Harrison, M.A., (), 36-40
[8] Hedlund, G.A., Remarks on the work of axel thue on sequences, Nord. mat. tidskr., 15, 148-150, (1967) · Zbl 0153.33101
[9] Knuth, D.E., The art of computer programming, vol 3: sorting and searching, (1973), Addison-Wesley Reading, MA · Zbl 0302.68010
[10] Knuth, D.E.; Morris, J.H.; Pratt, V.R., Fast pattern matching in strings, SIAM J. comput., 6, 323-350, (1977) · Zbl 0372.68005
[11] Lentin, A.; Schützenberger, M.P., A combinatorial problem in the theory of free monoids, Proc. university of north carolina, 128-144, (1967)
[12] 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
[13] Main, M.; Lorentz, R., An O(n log n) algorithm for finding repetition in a string, ()
[14] McCreight, E.M., A space economical suffix tree construction algorithm, J. ACM, 23, 262-272, (1976) · Zbl 0329.68042
[15] Peterson, M.; Hewitt, C.E., Comparative schematology, (), 119-127 · Zbl 0401.68002
[16] Thue, A., Über die gegenseitige lage gleicher teile gewisser zeichenreichen, Skr. vid.-kristiana I. mat. naturv. klasse, 1, 1-67, (1912) · JFM 44.0462.01
[17] Weiner, P., Linear pattern matching algorithms, Proc. 14th annual symposium on switching and automata theory, 1-11, (1973)
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.