Efficient parallel algorithms to test square-freeness and factorize strings. (English) Zbl 0736.68033

Summary: A string is square-free iff it does not contain a nonempty subword of the form \(ww\). We give an algorithm testing square-freeness of string in \(\log n\) time with \(n\) processors of a CRCW PRAM. The input alphabet is not bounded. The best sequential time algorithm for this problem takes \(O(n \log n)\) time. Hence the total number of operations in our parallel algorithm matches that of the best sequential algorithm. The algorithm relies on an efficient parallel computation of a factorization of words used in text compression.


68W15 Distributed algorithms
68R05 Combinatorics in computer science
68U15 Computing methodologies for text processing; mathematical typography


Full Text: DOI


[1] Apostolico, A., A myriad virtues of suffix trees, (Apostolico, A.; Galil, Z., Combinatorial Algorithms on Words (1985), Springer: Springer Berlin), 85-96
[2] Apostolico, A., Optimal parallel detection of squares in strings (1990), University of L’Aquilla, Manuscript
[3] 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
[4] Apostolico, A.; Preparata, F. P., Optimal off-line detection of repetitions in a string, Theoret. Comput. Sci., 22, 297-315 (1983) · Zbl 0497.68052
[5] Crochemore, M., An optimal algorithm for computing the repetitions in a word, Inform. Process. Lett., 12, 244-250 (1981) · Zbl 0467.68075
[6] Crochemore, M., Transducers and repetitions, Theoret. Comput. Sci., 45, 63-86 (1986) · Zbl 0615.68053
[7] Crochemore, M., Data compression with substitution, (Gross; Perrin, D., Electronics Dictionaries and Automata in Computational Linguistics, 377 (1989), Springer: Springer Berlin), 1-16, Lecture Notes in Computer Science
[8] Crochemore, M.; Rytter, W., Parallel computations on strings and arrays, (Choffrut; Lengauer, STACS’90. STACS’90, Lecture Notes in Computer Science, 415 (1990), Springer: Springer Berlin), 109-123
[9] Gibbons, A.; Rytter, W., Efficient Parallel Algorithms (1988), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0771.68015
[10] Lothaire, L., Combinatorics on Words (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0514.20045
[11] Main, M. G.; Lorentz, R. J., An \(O(n\) log \(n)\) algorithm for finding all repetitions in a string, J. Algorithms, 5, 422-432 (1984) · Zbl 0547.68083
[12] Main, M. G.; Lorentz, R. J., Linear time recognition of square-free strings, (Apostolico, A.; Galil, Z., Combinatorial Algorithms on Words (1985), Springer: Springer Berlin)
[13] Shiloach, Y.; Vishkin, U., An O(log \(n)\) parallel connectivity algorithm, J. Algorithms, 2, 57-63 (1981) · Zbl 0494.68070
[14] Ziv, J.; Lempel, A., A universal algorithm for sequential data compression, IEEE Trans. Inform. Theory, 23, 3, 337-343 (1977) · Zbl 0379.94010
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.