A constant-time optimal parallel string-matching algorithm

ABSTRACT

Given a pattern string, we describe a way to preprocess it. We design a constant-time optimal parallel algorithm for finding all occurences 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: 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]
• 5: 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]
• 6: 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]
• 7: 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]
• 8: 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
• 9: 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]
• 10: Lovasz, L. (1975), On the ratio of optimal integral and fractional covers, Discrete Math 13, 383-390.
• 11: Lyndon, R. C. and Schutzenberger, M. P. (1962), The equation aM = bNcP in a free group, Michigan Math. J. 9, 289- 298.
• 12: Morphy, O. (1968), Some modern mathematical methods in the theory of lion hunting, Amer. Math. Monthly 75, 185-187.
• 13: P6tard, H. (1938), A contribution to the mathematical theory of big game hunting, Amer. Math. Monthly #5.
• 14: Mosinzon Y. (1952), Hassamba, Hebrew children book.
• 15: Valiant, L. G. (1975), Parallelism in comparison models, SIAM J. Comput. #, 348-355.
• 16: 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]
• 17: 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:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

General Terms:
Algorithms, Performance, Theory