Optimal parallel detection of squares in strings. (English) Zbl 0748.68022

Apostolico, Alberto

Algorithmica 8, No. 4, 285-319 (1992).

Summary: A string \(w\) is primitive if it is not a power of another string (i.e., writing \(w=v^ k\) implies \(k=1\)). Conversely, \(w\) is a square if \(w=vv\), with \(v\) a primitive string. A string \(x\) is square-free if it has no nonempty substring of the form \(ww\). It is shown that the square-freedom of a string of \(n\) symbols over an arbitrary alphabet can be tested by a CRCW PRAM with \(n\) processors in \(O(\log n)\) time and linear auxiliary space. If the cardinality of the input alphabet is bounded by a constant independent of the input size, then the number of processors can be reduced to \(n/\log n\) without affecting the time complexity of this strategy. The fastest sequential algorithms solve this problem in \(O(n \log n)\) or \(O(n)\) time, depending on whether the cardinality of the input alphabet is unbounded or bounded, and either performance is known to be optimal within its class. More elaborate constructions lead to a CRCW PRAM algorithm for detecting within the same \(n\)-processors bounds, all positioned squares in \(x\) in time \(O(\log n)\) and using linear auxiliary space. The fastest sequential algorithms solve this problem in \(O(n \log n)\) time, and such a performance is known to be optimal.

MSC:

68W15	Distributed algorithms
68Q25	Analysis of algorithms and problem complexity
68R15	Combinatorics on words

Keywords:

combinatorial algorithms on words; string matching; avoidable regularities; squares and repetitions in a string

References:

[1]	Apostolico, A., On Context-Constrained Squares and Repetitions in a String, RAIRO Inform. Théor., 18, 147-159 (1984) · Zbl 0543.68067
[2]	Apostolico, A.; Atallah, M. J.; Larmore, L. L.; McFaddin, H. S., Efficient Parallel Algorithms for String Editing and Related Problems, SIAM J. Comput., 19, 5, 968-988 (1990) · Zbl 0711.68055
[3]	Apostolico, A.; Galil, Z., Combinatorial Algorithms on Words (1985), Berlin: Springer-Verlag, Berlin · Zbl 0564.00027
[4]	Apostolico, A.; Iliopoulos, C.; Landau, G.; Schieber, B.; Vishkin, U., Parallel Construction of a Suffix Tree, with Applications, Algorithmica, 3, 347-365 (1988) · Zbl 0646.68080
[5]	Apostolico, A.; Preparata, F. P., Optimal Off-Line Detection of Repetitions in a String, Theoret. Comput. Sci., 22, 297-315 (1983) · Zbl 0497.68052
[6]	Apostolico, A.; Preparata, F. P., Structural Properties of the String Stratistics Problem, J. Comput. System. Sci., 31, 3, 394-411 (1985) · Zbl 0593.68047
[7]	O. Berkman, D. Breslauer, Z, Galil, B. Schieber, and U. Vishkin, Hightly Parallelizable Problems,Proceedings of the 21st ACM Symposium on Theory of Computing, Seattle, Wash., May 1989, pp. 309-319.
[8]	Chen, K. T.; Fox, R. H.; Lyndon, R. C., Free Differential Calculus, IV, Ann. of Math., 68, 81-95 (1958) · Zbl 0142.22304
[9]	Crochemore, M., An Optimal Algorithm for Computing the Repetitions in a Word, Inform. Process. Lett., 12, 5, 244-250 (1981) · Zbl 0467.68075
[10]	Crochemore, M., Recherche Linearire d’un Carré dans un Mot, C. R. Acad. Sci. Paris Sér. I, 296, 781-784 (1983) · Zbl 0522.68074
[11]	Crochemore, M.; Rytter, W., Usefulness of the Karp-Miller-Rosenberg Strategy in the Design of Parallel Algorithms, Theoret. Comput. Sci., 88, 59-82 (1991) · Zbl 0737.68037
[12]	Duval, J. P., Factorizing Words over an Ordered Alphabet, J. Algorithms, 4, 363-381 (1983) · Zbl 0532.68061
[13]	F. E. Fich, R. L. Ragde, and A. Wigderson, Relations between Concurrent-Write Models of Parallel Computation,Proceedings of the 3rd A CM Symposium on Principles of Distributed Computing, Vancouver, B.C., Aug. 27-29, 1984, pp. 179-184. · Zbl 0652.68065
[14]	Lothaire, M., Combinatorics on Words (1982), Reading, Mass.: Addison-Wesley, Reading, Mass. · Zbl 1001.68093
[15]	Lyndon, R. C.; Shutzenberger, M. P., The Equationa^M= b^Nc^P in a Free Group, Michigan Math. J., 9, 289-298 (1962) · Zbl 0106.02204
[16]	Main, M. G.; Lorentz, R. J., AnO(n logn) Algorithm for Finding all Repetitions in a String, J. Algorithms, 5, 422-432 (1985)
[17]	Main, M. G.; Lorentz, R. J.; Apostolico, A.; Galil, Z., Linear-Time Recognition of Square-Free Strings, Combinatorial Algorithms on Words, 271-278 (1985), Berlin: Springer-Verlag, Berlin
[18]	Rabin, M.; Apostolico, A.; Galil, Z., Discovering Repetitions in Strings, Combinatorial Algorithms on Words, 279-288 (1985), Berlin: Springer-Verlag, Berlin
[19]	Thue, A., Über unendliche Zeichenreihen, Norske Vid. Selsk. I Mat. Natur. Kl. Skr., no. 7, 1-22 (1906) · JFM 37.0066.17
[20]	Thue, A., Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk. I Mat.-Natur. Kl. Skr., no. 1, 1-67 (1912) · JFM 43.0162.07
[21]	Wong, C. K.; Chandra, A. K., Bounds for the String Editing Problem, J. Assoc. Comput. Mach., 23, 1, 13-16 (1976) · Zbl 0316.68019