A constant-time optimal parallel string-matching algorithm

ABSTRACT

Given a pattern string, we describe a way to preprocess it. We design a CRCW-PRAM constant time optimal parallel algorithm for finding all occurrences of the (preprocessed) pattern in any given text.

REFERENCES

• 1: Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
• 2: Dany Breslauer , Zvi Galil, An optimal O(log n)time parallel string matching algorithm, SIAM Journal on Computing, v.19 n.6, p.1051-1058, Dec. 1990 [doi>10.1137/0219072]
• 3: Dany Breslauer , Zvi Galil, A lower bound for parallel string matching, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.439-443, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103465]
• 4: ~Cot.E, R., CROCHEMORE, M. A., GALIL, Z.. GASlENIEC, L., HARIHARAN, R., MUTHUKRISHNAN, S., ~PARK, K., AND RYTTER, W. 1993. Optimally fast parallel algorithms for preprocessing and ~pattern matching in one and two dimensions. In Proceedings of the 34th {EEE Symposium on ~Foundations of Computer Science. IEEE, New York, pp. 248-258.
• 5: Stephen Cook , Cynthia Dwork , Ru&duml;ger Reischuk, Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM Journal on Computing, v.15 n.1, p.87-97, Feb. 1986 [doi>10.1137/0215006]
• 6: Artur Czumaj , Zvi Galil , Leszek Gąsieniec , Kunsoo Park , Wojciech Plandowski, Work-time-optimal parallel algorithms for string problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.713-722, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225289]
• 7: Faith E. Fich , Prabhakar L. Ragde , Avi Wigderson, Relations between concurrent-write models of parallel computation, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.179-189, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806745]
• 8: Zvi Galil, Optimal parallel algorithms for string matching, Information and Control, v.67 n.1-3, p.144-157, Oct./Nov./Dec. 1986 [doi>10.1016/S0019-9958(85)80031-0]
• 9: 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]
• 10: Richard M. Karp , Michael O. Rabin, Efficient randomized pattern-matching algorithms, IBM Journal of Research and Development, v.31 n.2, p.249-260, March 1987
• 11: Z. M. Kedem , G. M. Landau , K. V. Palem, Optimal parallel suffix-prefix matching algorithm and applications, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.388-398, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72977]
• 12: LOVASZ, L. 1975. On the ratio of optimal integral and fractional covers. Disc. Math. 13, 383-390.
• 13: LYNDON, R. C., AND SCHUTZENBERGER, M. P. 1962. The equation aM = br~cP in a free group. ~Mich. Math J. 9, 289-298.
• 14: ~MORPHY, O. 1968. A contribution to the mathematical methods in the theory of lion hunting. ~~lnz Math. Monthly 75, 185-187.
• 15: ~MOSINZON, Y. 1952. ttassamba. Hebrew children's book.
• 16: ~PETARD, H. t938. A contribution to the mathematical theory of big game hunting. Am. Math. ~Monthly 45.
• 17: ~VALIANT, L. O. 1975. Parallelism in comparison models. SIAMJ, Comput. 4, 348-355.
• 18: Uzi Vishkin, Optimal parallel pattern matching in strings, Information and Control, v.67 n.1-3, p.91-113, Oct./Nov./Dec. 1986 [doi>10.1016/S0019-9958(85)80028-0]
• 19: Uzi Vishkin, Deterministic sampling: a new technique for fast pattern matching, SIAM Journal on Computing, v.20 n.1, p.22-40, Feb. 1991 [doi>10.1137/0220002]

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:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory

Keywords:
CRCW-PRAM, constant time, lion hunting, optimal parallel algorithm, period, string matching