Optimal parallel algorithms for string matching

ABSTRACT

Let WRAM [PRAM] be a parallel computer with p processors (RAM's) which share a common memory and are allowed simultaneous reads and writes [only simultaneous reads]. The only type of simultaneous writes allowed is a simultaneous AND: several processors may write O simultaneously into the same memory cell. Let t be the time bound of the computer. We design below families of parallel algorithms that solve the string matching problem with inputs of size n (n is the sum of lengths of the pattern and the text) and have the following performance in terms of p, t and n: 1. For WRAM: pt &equil; O(n) for for p ≤ n/log n. 2. For PRAM: pt &equil; O(n) for P ≤ n/log2n. 3. For WRAM: t &equil; constant for p &equil; nl+&egr; and any &egr; > O. 4. For WRAM: t &equil; O(log n/log log n) for p &equil; n. Similar families are also obtained for the problem of finding all initial palindromes of a given string.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: A. Borodin , J. E. Hopcroft, Routing, merging and sorting on parallel models of computation, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.338-344, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802209]
• 3: Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
• 4: I. Bar-On and U. Vishkin, Optimal parallel generation of a computation tree form, Manuscript, Department of Computer Science, Courant Institute, October 1983.
• 5: Stephen Cook , Cynthia Dwork, Bounds on the time for parallel RAM's to compute simple functions, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.231-233, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802196]
• 6: M.J. Fischer and M.S. Paterson, String-matching and other products, in Complexity and Computation, SIAMAMS Proceedings 7 (R.M. Karp, Ed.), pp. 113-125, American Mathematical Society, Providence, R.I., 1974.
• 7: F.E. Fich, R.L. Ragde and A. Wigderson, Relations between concurrent-write models of parallel computation, Manuscript, November 1983.
• 8: Z. Galil and J.I. Seiferas, Time-space-optimal string matching, JCSS 26 (1983), pp. 280-294.
• 9: D.E. Knuth, J.H. Morris and V.R. Pratt, Fast pattern matching in strings, SIAM J. Comput. 6 (1977), pp. 322-350.
• 10: Richard M. Karp , Raymond E. Miller , Arnold L. Rosenberg, Rapid identification of repeated patterns in strings, trees and arrays, Proceedings of the fourth annual ACM symposium on Theory of computing, p.125-136, May 01-03, 1972, Denver, Colorado, United States [doi>10.1145/800152.804905]
• 11: R.M. Karp and M.O. Rabin, Efficient randomized pattern-matching algorithms, a manuscript.
• 12: R.C. Lyndon and M.P. Schutzenberger, The equation aM &equil; bNcP in a free group, Michigan Math. J. 9 (1962), 289-298.
• 13: F.P. Preparata and J. Vuillemin, The cube-connected-cycles: a versatile network for parallel computation, Proc. 20th IEEE FOCS (1979), pp. 140-147.
• 14: Y. Shiloach and U. Vishkin, Finding the maximum, merging and sorting in a parallel computation model, J. of Algorithms 2 (1981), pp. 88-102.
• 15: L.G. Valiat, Parallelism in comparison problems, SIAM J. on Computing 4 (1975), pp. 348-355.
• 16: U. Vishkin, An optimal parallel algorithm for selection, Manuscript, Department of Computer Science, Courant Institute, December 1983.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Theory