{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:11Z","timestamp":1787337491001,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>\n                    We give an alphabet-independent deterministic parallel algorithm for finding all occurrences of a pattern array of size m\n                    <jats:sub>h<\/jats:sub>\n                    x m\n                    <jats:sub>w<\/jats:sub>\n                    in a text array of size n\n                    <jats:sub>h<\/jats:sub>\n                    x n\n                    <jats:sub>w<\/jats:sub>\n                    in the concurrent-read-concurrent-write--parallel-random-access-machine (CRCW--PRAM) model. Our algorithm runs in O(1) time performing optimal, that is, O(n\n                    <jats:sub>h<\/jats:sub>\n                    x n\n                    <jats:sub>w<\/jats:sub>\n                    ) work, following preprocessing of the pattern. This improves the previous best bound of O(log log m ) time with optimal work [A. Amir, G. Benson, and M. Farach, Proceedings 5th Annual ACM Symposium on Parallel Algorithms and Architectures, ACM, New York, 1993, pp. 79--85], following preprocessing of the pattern, where m=max{m\n                    <jats:sub>h<\/jats:sub>\n                    , m\n                    <jats:sub>w<\/jats:sub>\n                    }.\n                  <\/jats:p>\n                  <jats:p>\n                    The preprocessing required by our algorithm (and that due to Amir, Benson, and Farach) can be accomplished in O(log log m) time and O(m\n                    <jats:sub>h<\/jats:sub>\n                    x m\n                    <jats:sub>w<\/jats:sub>\n                    ) work [M. Crochemore et al., manuscript, 1993], [R. Cole et al., manuscript, 1993].\n                  <\/jats:p>","DOI":"10.1137\/s0097539795280068","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"668-681","source":"Crossref","is-referenced-by-count":12,"title":["A Constant Time Optimal Parallel Algorithm for Two-Dimensional Pattern Matching"],"prefix":"10.1137","volume":"27","author":[{"given":"Maxime","family":"Crochemore","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leszek","family":"Gasieniec","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ramesh","family":"Hariharan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S.","family":"Muthukrishnan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wojciech","family":"Rytter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"A. Amir, G. Benson,\n                      Two dimensional periodicity in rectangular arrays\n                      , Proceedings of the 3rd ACM Symposium on Discrete Algorithms, 1992, pp. 440\u2013452."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"A. Amir, G. Benson, M. Farach,\n                      Alphabet independent two dimensional matching\n                      , Proceedings of the 24th ACM Symposium on Theory of Computing, 1992, pp. 59\u201368.","DOI":"10.1145\/129712.129719"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"A. Amir, G. Benson, M. Farach\n                      Parallel two dimensional matching in logarithmic time\n                      Proceedings of the 5th ACM Symposium on Parallel Algorithms and Architectures, 1993, pp. 79\u201385.","DOI":"10.1145\/165231.165242"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"A. Apostolico, D. Breslauer, Z. Galil,\n                      Optimal parallel algorithms for periods, palindromes and squares\n                      , Proceedings of the 19th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 623, 1992, pp. 296\u2013307.","DOI":"10.1007\/3-540-55719-9_82"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90318-V"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/0207043"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"R. S. Bird,\n                      Two dimensional pattern matching\n                      , Information Processing Letters, Vol. 6, No. 5, 1977, pp. 168\u2013170.","DOI":"10.1016\/0020-0190(77)90017-5"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0219072"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/0221050"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Richard Cole, Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions, IEEE Comput. Soc. Press, Los Alamitos, CA, 1993, 248\u20132581328425","DOI":"10.1109\/SFCS.1993.366862"},{"key":"R11","unstructured":"M. Crochemore, L. Ga\u00b8sieniec, Z. Galil, K. Park, W. Rytter,\n                      Constant time Deterministic Sample computation and its applications\n                      , Manuscript, 1993."},{"key":"R12","unstructured":"R. Cole, Z. Galil, R. Hariharan, S. Muthukrishnan, and K. Park,\n                      Optimal parallel two dimensional witness computation\n                      , Manuscript, 1993."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90073-B"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"M. Crochemore, W. Rytter,\n                      On linear\u2010time alphabet\u2010independent 2\u2010dimensional pattern matching\n                      , LATIN\u201995, LNCS 911, Springer\u2010Verlag, 1995, pp. 220\u2013229.","DOI":"10.1007\/3-540-59175-3_91"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0217037"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80031-0"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"Z. Galil,\n                      Hunting lions in the desert optimally or A constant\u2010time optimal parallel string matching algorithm\n                      Proceedings of the 24th ACM Symposium on Theory of Computing, 1992, pp. 69\u201376.","DOI":"10.1145\/129712.129720"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"Z. Galil, K. Park,\n                      Truly alphabet\u2010independent two dimensional matching\n                      , Proceedings of the 33rd Annual IEEE Symposium on the Foundations of Computer Science, 1992, pp. 247\u2013256.","DOI":"10.1109\/SFCS.1992.267767"},{"key":"R19","volume-title":"Introduction to parallel algorithms","author":"Xavier C.","year":"1998"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Z. Kedem, G. Landau, K. Palem,\n                      Optimal parallel suffix\u2010prefix matching algorithm and application\n                      , Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, 1989, pp. 388\u2013398.","DOI":"10.1145\/72935.72977"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"R. M. Karp, R. E. Miller, A. L. Rosenberg,\n                      Rapid identification of repeated patterns in strings, trees and arrays\n                      Proceedings of the 4th ACM Symposium on Theory of Computing, 1972, pp. 125\u2013136.","DOI":"10.1145\/800152.804905"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1147\/rd.312.0249"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1307\/mmj\/1028998766"},{"key":"R24","unstructured":"T. Mathies,\n                      A fast parallel algorithm to determine edit distance\n                      , TR CMU\u2010CS\u201088\u2010130, CMU, 1988."},{"key":"R25","doi-asserted-by":"crossref","unstructured":"Prabhakar Ragde, The parallel simplicity of compaction and chaining, Lecture Notes in Comput. Sci., Vol. 443, Springer, New York, 1990, 744\u20137511076846","DOI":"10.1007\/BFb0032071"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1215\/ijm\/1255631807"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80028-0"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"U. Vishkin,\n                      Deterministic sampling \u2013 A new technique for fast pattern matching\n                      , Proc. of the 22nd ACM Symposium on Theory of Computing, 1990, pp. 170\u2013180.","DOI":"10.1145\/100216.100235"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539795280068","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:13:35Z","timestamp":1787336015000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795280068"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539795280068"],"URL":"https:\/\/doi.org\/10.1137\/s0097539795280068","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}