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

Crochemore, Maxime; Rytter, Wojciech

Inf. Process. Lett. 38, No. 2, 57-60 (1991).

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.

MSC:

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

Keywords:

CRCW PRAM

References:

[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