×
Breslauer, D.; Galil, Z.

Finding all periods and initial palindromes of a string in parallel. (English) Zbl 0833.68053

Algorithmica 14, No. 4, 355-366 (1995).
Summary: An optimal \(O(\log\log n)\)-time CRCW-PRAM algorithm for computing all period lengths of a string is presented. Previous parallel algorithms compute the period only if it is shorter than half of the length of the string. The algorithm can be used to find all initial palindromes of a string in the same time and processor bounds. Both algorithms are the fastest possible over a general alphabet. We derive a lower bound for finding initial palindromes by modifying a known lower bound for finding the period length of a string. When \(p\) processors are available the bounds become \(\Theta(\lceil n/p\rceil+ \log\log_{\lceil 1+ p/n\rceil}2p)\).

Cited in 18 Documents

MSC:

68W10 Parallel algorithms in computer science
68W15 Distributed algorithms
68R15 Combinatorics on words
68Q25 Analysis of algorithms and problem complexity

Keywords:

CRCW-PRAM algorithm
PDF BibTeX XML Cite
\textit{D. Breslauer} and \textit{Z. Galil}, Algorithmica 14, No. 4, 355--366 (1995; Zbl 0833.68053)
Full Text: DOI

References:

[1] A. Apostolico and D. Breslauer. An optimalO(log logn) time parallel algorithm for detecting all squares in a string.SIAM J. Comput., to appear. · Zbl 0864.68045
[2] A. Apostolico, D. Breslauer, and Z. Galil. Optimal parallel algorithms for periods, palindromes and squares.Proc. 19th Internat. Colloq. on Automata, Languages, and Programming. Lecture Notes in Computer Science, Vol. 623. Springer-Verlag, Berlin, 1992, pages 296-307.
[3] H. W. Bergerson.Palindromes and Anagrams. Dover. New York, 1973.
[4] R. P. Brent. Evaluation of general arithmetic expressions.J. Assoc. Comput. Mach., 21:201-206, 1974. · Zbl 0276.68010
[5] D. Breslauer. Efficient String Algorithmics. Ph.D. thesis, Department of Computer Science, Columbia University, New York, 1992. · Zbl 0795.68079
[6] D. Breslauer. Fast parallel string prefix-matching.Theoret. Comput. Sci., 137(2):269-278, 1995. · Zbl 0873.68072
[7] D. Breslauer. Testing string superprimitivity in parallel.Inform. Process. Lett., 49:5 235-241, 1994. · Zbl 0795.68092
[8] D. Breslauer and Z. Galil. An optimalO(log logn) time parallel string matching algorithm.SIAM J. Comput., 19(6): 1051-1058, 1990. · Zbl 0711.68057
[9] D. Breslauer and Z. Galil. A lower bound for parallel string matching.SIAM J. Comput., 21(5):856-862. 1992. · Zbl 0756.68048
[10] M. Crochemore and W. Rytter. Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays.Theoret. Comput. Sci., 88:59-82, 1991. · Zbl 0737.68037
[11] F. E. Fich, R. L. Radge, and A. Wigderson. Relations between concurrent-write models of parallel computation.Proc. 3rd ACM Symp. on Principles of Distributed Computing, 1984, pages 179-189.
[12] M. J. Fischer and M. S. Paterson. Sring matching and other produces. In R. M. Karp, editor,Complexity of Computation. American Mathematical Society, Providence, RI, 1974, pages 113-125.
[13] G. Galil. Optimal parallel algorithms for string matching.Inform. and Control. 67:144-157, 1985. · Zbl 0588.68022
[14] J. E. Hopcroft and J. D. Ullman.Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, MA, 1979. · Zbl 0426.68001
[15] R. M. Karp, R. E. Miller, and A. L. Rosenberg. Rapid identification of repeated patterns in strings, trees and arrays.Proc. 4th ACM Symp. on Theory of Computing, 1972, pages 125-136. · Zbl 0354.68119
[16] Z. Kedem, G. M. Landau, and K. Palem. Optimal parallel suffix-prefix matching algorithm and applications.Proc. 1st ACM Symp. on Parallel Algorithms and Architectures, 1989, pages 388-398. · Zbl 0858.68089
[17] D. E. Knuth, J. H. Morris, and V. R. Pratt. Fast pattern matching in strings.SIAM J. Comput., 6:322-350, 1977. · Zbl 0372.68005
[18] M. Lothaire.Combinatorics on Words. Addison-Wesley, Reading, MA, 1983. · Zbl 0514.20045
[19] R. C. Lyndon and M. P. Schutzenberger. The equation am=bncp in a free group.Michigan Math. J., 9:289-298, 1962. · Zbl 0106.02204
[20] G. Manacher. A new linear-time ?On-line? algorithm for finding the smallest initial palindrome of a string.J. Assoc. Comput. Mach., 22:346-351, 1975. · Zbl 0305.68027
[21] L. G. Valiant. Parallelism in comparison models.SIAM J. Comput., 4:348-355, 1975. · Zbl 0311.68033
[22] U. Vishkin. Optimal parallel pattern matching in strings.Inform. and Control, 67:91-113, 1985. · Zbl 0588.68023
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.