Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays. (English) Zbl 0737.68037

Crochemore, Maxime; Rytter, Wojciech

Theor. Comput. Sci. 88, No. 1, 59-82 (1991).

The authors reconsider the Karp-Miller-Rosenberg (KMR) sequential algorithm for strings and pattern matching as a basic technique in parallel computation.
The main result is a parallel version of the KMR algorithm computing the dictionary of basic factors of a string. Its complexity is \(O(\log(n)^ 2)\) time (\(n\) processors) on a CREW-PRAM model and \(O(\log n)\) (\(n\) processors) on a CRCW-PRAM model. This algorithm is used as a general framework for designing a large class of parallel algorithms for strings and arrays. Using the KMR parallel algorithm, the following problems are studied in the paper:
1. Searching for squares in strings.
2. Testing even palstars and compositions of \(k\)-palindromes (\(k=2,3,4\)) in a string.
3. Computing the maximal suffix and Lyndon factorization of a string.
4. Pattern matching in strings and arrays finding the longest repeated factor of a string, finding the maximal common factor of two strings, finding the longest symmetric factor of a string.
The authors prove that all problems can be solved by parallel algorithms with the complexity of the KMR algorithm. Related to these problems, three open problems are presented at the end of the paper.

Reviewer: B.Corneliu (Iaşi)

MSC:

68W15

Distributed algorithms

Keywords:

parallel complexity; pattern; pattern matching; CREW-PRAM; CRCW-PRAM; strings

References:

[1]	Aho, A.; Corasick, M., Efficient string-matching: an aid to bibliographic search, Comm. ACM, 18, 333-340 (1975) · Zbl 0301.68048
[2]	Aho, A.; Hopcroft, J.; Ullman, J., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley
[3]	Apostolico, A., On context-constrained squares and repetitions in a string, RAIRO Inform. Theor. Appl., 18, 147-159 (1984) · Zbl 0543.68067
[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]	Baker, T., A technique for extending rapid exact string matching to arrays of more than one dimension, SIAM J. Comput., 7, 533-541 (1978) · Zbl 0387.68031
[6]	Bird, R. S., Two-dimensional pattern-matching, Inform. Process. Lett., 6, 168-170 (1977)
[7]	Boyer, R.; Moore, J., A fast string searching algorithm, Comm. ACM, 20 (1977) · Zbl 1219.68165
[8]	Cole, R., Parallel merge sort, Found. Comput. Sci. (1987) · Zbl 0799.68055
[9]	Crochemore, M., An optimal algorithm for computing the repetitions in a word, Inform. Process. Lett., 12 (1981) · Zbl 0467.68075
[10]	Crochemore, M., Transducers and repetitions, Theoret. Comput. Sci., 45, 63-86 (1986) · Zbl 0615.68053
[12]	Crochemore, M., String matching and periods, EATCS Bulletin, 39, 149-153 (1989) · Zbl 0693.68025
[14]	Duval, J., Factorizing words over an ordered alphabet, J. Algorithms, 4, 363-381 (1983) · Zbl 0532.68061
[15]	Galil, Z., Open problems in stringology, (Apostolico, A.; Galil, Z., Combinatorial algorithms on words (1985), Springer: Springer Berlin), 1-12 · Zbl 0607.68054
[16]	Galil, Z., Optimal parallel algorithm for string matching, Inform. and Control, 67, 144-157 (1985) · Zbl 0588.68022
[17]	Galil, Z.; Seiferas, J., A linear time on-line recognition algorithm for palstars, J. ACM, 25, 102-111 (1978) · Zbl 0365.68058
[18]	Galil, Z.; Seiferas, J., Time space optimal string matching, J. Comput. System Sci., 26, 280-294 (1983) · Zbl 0509.68101
[19]	Gibbons, A.; Rytter, W., Efficient Parallel Algorithms (1988), Cambridge University Press · Zbl 0771.68015
[20]	Karp, R.; Miller, R.; Rosenberg, A., Rapid identification of repeated patterns in strings, arrays and trees, Proc. of ACM Symp. on Theory Comput., 4, 125-136 (1972)
[21]	Knuth, D.; Morris, J.; Pratt, V., Fast pattern matching in strings, SIAM J. Comput., 6, 322-350 (1977) · Zbl 0372.68005
[23]	Lothaire, M., Combinatorics on Words (1983), Addison-Wesley · Zbl 0514.20045
[24]	Main, M.; Lorentz, R., An \(O(n\) log \(n)\) algorithm for finding all repetitions in a string, J. Algorithms, 422-432 (1984) · Zbl 0547.68083
[25]	Main, M.; Lorentz, R., Linear time recognition of square-free strings, (Apostolico, A.; Galil, Z., Combinatorial algorithms on words (1985), Springer: Springer Berlin), 271-278
[26]	Manacher, G., A new linear time on-line algorithm for finding the smallest initial palindrome of the string, J. ACM, 22, 345-351 (1975) · Zbl 0305.68027
[27]	Rytter, W., On the parallel transformations of regular expressions to nondeterministic finite automata, Inform. Process. Lett., 31, 103-109 (1989) · Zbl 0682.68060
[28]	Vishkin, U., Optimal parallel pattern matching in strings, Inform. and Control, 67, 91-113 (1985) · Zbl 0588.68023