On context constrained squares and repetitions in a string. (English) Zbl 0543.68067

Summary: Some combinatorial and computational problems concerning repetitions and repetition roots in a string x on a finite alphabet - that are characterized in general by an O(n log n) bound in terms of the length n of x - are shown to admit of a linear bound when approached in particular contexts. More precisely, it is shown that the number of distinct repetition roots u that are bond to the occurrence of their cube \(u^ 3\) somewhere along the textstring is bounded by n, whence this same bound an be drawn for the number of distinct cube substrings appearing in a generic string. Constraints of similar nature are also discussed that guarantee linear time square-free recognition, and a linear time strategy is proposed to detect, in correspondence with each primitive root u that meets such conditions on x, and for all possible forms of u-rooted repetitions in x, the leftmost occurring repetition in this form.


68T99 Artificial intelligence
68Q25 Analysis of algorithms and problem complexity
Full Text: EuDML


[1] 1. A. THUE, Uber Die Gegenseitige Lage Gleicher Teile Gewisser Zeichenreichen, Skr. Vid.-Kristiana I. Mat. Naturv. Klasse, Vol. 1, 1912, pp. 1-67 JFM44.0462.01 · JFM 44.0462.01
[2] 2. M. MAIN and R. LORENTZ, An O (n log n) Algorithm for Finding Repetition in a String. T.R. 79-056, Comp. Sc. Dept., Washington State Univ., Pullman, 1972.
[3] 3. M. CROCHEMORE, An Optimal Algorithm for Computing the Repetitions in a Word, Information Processing Letters, Vol. 12, 1981, pp. 244-250. Zbl0467.68075 MR632873 · Zbl 0467.68075
[4] 4. A. APOSTOLICO and F. P. PREPARATA, Optimal Off-Line Detection of Repetitions in a String, Theoretical Computer Science, Vol. 22, 1983, pp. 237-315. Zbl0497.68052 MR693062 · Zbl 0497.68052
[5] 5. A. LENTIN and M. P. SCHUTZEMBERGER, A Combinatorial Problem in the Theory of Free Monoids, in Combinatorial Mathematics and its Applications, University of North Carolina Press, N.C., 1969, pp. 128-144. Zbl0221.20076 · Zbl 0221.20076
[6] 6. A. APOSTOLICO and F. P. PREPARATA, A Structure for the Statistics of All Substrings of a Textstring With or Without Overlap. Proceedings of the 2nd World Conference on Mathematics at the Service of Man, Las Palmas (Canary Islands), 1982. Zbl0503.68064 · Zbl 0503.68064
[7] 7. E. M. MCCREIGHT, A Space Economical Suffix Tree Construction Algorithm, J. of the ACM, Vol. 23, 1976, pp. 262-272. Zbl0329.68042 MR413594 · Zbl 0329.68042
[8] 8. R. C. LYNDON and M. P. SCHUTZEMBERGER, The Equation aM = bN cP in a Free Group, Michigan Mathemat. Journal, Vol. 9, 1962, pp. 289-298 Zbl0106.02204 MR162838 · Zbl 0106.02204
[9] 9. A. V. AHO, J. E. HOPCROFT and J. D. ULLMAN, The Design and Analysis of Computer Algorithms, Addison-Wesley, MA, 1974. Zbl0326.68005 MR413592 · Zbl 0326.68005
[10] 10. P. WEINER, Linear Pattern Matching Algorithms, Proceedings of the 14th Annual Symposium on Switching and Automata Theory, 1973, pp. 1-11 MR441032
[11] 11. D. E. KNUTH, The Art of Computer Programming, Vol. 3, Sorting and Searching, Addison-Wesley, MA, 1973. MR445948 · Zbl 0302.68010
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.