×

Parallel two dimensional witness computation. (English) Zbl 1078.68155

Summary: An optimal parallel CRCW-PRAM algorithm to compute witnesses for all non-period vectors of an \(m_1\times m_2\) pattern is given. The algorithm takes \(O(\log \log m)\) time and does \(O(m_1\times m_2)\) work, where \(m=\max\{m_1,m_2\}\). This yields a work optimal algorithm for 2D pattern matching which takes \(O(\log\log m)\) preprocessing time and \(O(1)\) text processing time.

MSC:

68W10 Parallel algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Amir, A.; Benson, G., Two dimensional periodicity, SIAM J. Comput., 27, 90-106 (1998) · Zbl 0907.68108
[2] Amir, A.; Benson, G.; Farach, M., An alphabet independent approach to two dimensional pattern matching, SIAM J. Comput., 23, 313-323 (1994) · Zbl 0804.68056
[3] Amir, A.; Benson, G.; Farach, M., Optimal parallel two dimensional text searching on a CREW, Inf. Comput., 144, 1-17 (1998) · Zbl 0917.68049
[4] A. Apostolico, D. Breslauer, Z. Galil, Optimal parallel algorithms for periods, palindromes and squares, in: Proceedings of the 19th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 623, 1992, pp. 296-307; A. Apostolico, D. Breslauer, Z. Galil, Optimal parallel algorithms for periods, palindromes and squares, in: Proceedings of the 19th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 623, 1992, pp. 296-307
[5] Baker, T. J., A technique for extending rapid exact-match 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, Inf. Process. Lett., 6, 5, 168-170 (1977)
[7] Breslauer, D.; Galil, Z., An optimal \(O( loglogm)\) time parallel string matching algorithm, SIAM J. Comput., 19, 1051-1058 (1990) · Zbl 0711.68057
[8] Breslauer, D.; Galil, Z., A lower bound for parallel string matching, SIAM J. Comput., 21, 856-862 (1992) · Zbl 0756.68048
[9] Crochemore, M.; Galil, Z.; Gasieniec, L.; Park, K.; Rytter, W., Constant-time randomized parallel string matching, SIAM J. Comput., 26, 4, 950-960 (1997) · Zbl 0885.68078
[10] Crochemore, M.; Gasieniec, L.; Hariharan, R.; Muthukrishnan, S.; Rytter, W., An optimal constant time parallel algorithm for 2D pattern matching, SIAM J. Comput., 27, 3, 668-681 (1998) · Zbl 0912.68067
[11] R. Cole, M. Crochemore, Z. Galil, L. Gasieniec, R. Hariharan, S. Muthukrishnan, K. Park, W. Rytter, Optimal parallel algorithms for preprocessing and pattern matching in one and two dimensions, in: Proceedings of the 34rd IEEE Symposium on the Foundations of Computer Science, 1993, pp. 248-257; R. Cole, M. Crochemore, Z. Galil, L. Gasieniec, R. Hariharan, S. Muthukrishnan, K. Park, W. Rytter, Optimal parallel algorithms for preprocessing and pattern matching in one and two dimensions, in: Proceedings of the 34rd IEEE Symposium on the Foundations of Computer Science, 1993, pp. 248-257
[12] Fich, F.; Ragde, R.; Widgerson, A., Relations between concurrent-write models of parallel computation, SIAM J. Comput., 17, 606-627 (1988) · Zbl 0652.68065
[13] L. Gasieniec, K. Park, Work-Time optimal parallel prefix matching, in: Proceedings of the European Symposium on Algorithms, 1994, pp. 471-482; L. Gasieniec, K. Park, Work-Time optimal parallel prefix matching, in: Proceedings of the European Symposium on Algorithms, 1994, pp. 471-482
[14] Galil, Z.; Park, K., Alphabet-independent two dimensional witness computation, SIAM J. Comput., 25, 907-935 (1996) · Zbl 0861.68032
[15] JaJa, J., Introduction to Parallel Algorithms (1991), Addison-Wesley: Addison-Wesley Reading, MA
[16] Kedem, Z.; Landau, G.; Palem, K., Parallel suffix-prefix-matching algorithm and application, SIAM J. Comput., 25, 998-1023 (1996) · Zbl 0858.68089
[17] Main, M. G.; Lorentz, R. J., An \(O(n\) log \(n)\) algorithm for finding all repetitions in a string, J. Algorithms, 5, 422-432 (1984) · Zbl 0547.68083
[18] Ragde, P., The parallel simplicity of compaction and chaining, J. Algorithms, 14, 371-380 (1993) · Zbl 0793.68072
[19] Vishkin, U., Optimal pattern matching in strings, Inf. Control, 67, 91-113 (1985) · Zbl 0588.68023
[20] Vishkin, U., Deterministic sampling—A new technique for fast pattern matching, SIAM J. Comput., 20, 22-40 (1991) · Zbl 0716.68074
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.