{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:27Z","timestamp":1787337507832,"version":"build-2736575974"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>String matching is rich with a variety of algorithmic tools. In contrast, multidimensional matching has had a rather sparse set of techniques. This paper presents a new algorithmic technique for two-dimensional matching: periodicity analysis. Its strength appears to lie in the fact that it is inherently two-dimensional.<\/jats:p>\n                  <jats:p>Periodicity in strings has been used to solve string matching problems. Multidimensional periodicity, however, is not as simple as it is in strings and was not formally studied or used in pattern matching. In this paper, we define and analyze two-dimensional periodicity in rectangular arrays. One definition of string periodicity is that a periodic string can self-overlap in a particular way. An analogous concept is true in two dimensions. The self-overlap vectors of a rectangle generate a regular pattern of locations where the rectangle may originate. Based on this regularity, we define four categories of periodic arrays--- nonperiodic, lattice periodic, line periodic, and radiant periodic---and prove theorems about the properties of the classes.<\/jats:p>\n                  <jats:p>\n                    We give serial and parallel algorithms that find all locations where an overlap originates. In addition, our algorithms find a witness proving that the array does not self-overlap in any other location. The serial algorithm runs in time O(m\n                    <jats:sup>2<\/jats:sup>\n                    ) (linear time) when the alphabet size is finite, and in O(m\n                    <jats:sup>2<\/jats:sup>\n                    log m) otherwise. The parallel algorithm runs in time O(log m) using O(m\n                    <jats:sup>2<\/jats:sup>\n                    ) CRCW processors.\n                  <\/jats:p>","DOI":"10.1137\/s0097539795298321","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"90-106","source":"Crossref","is-referenced-by-count":43,"title":["Two-Dimensional Periodicity in Rectangular Arrays"],"prefix":"10.1137","volume":"27","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gary","family":"Benson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"A. Amir and G. Benson,\n                      Two\u2010dimensional periodicity and its application\n                      , in 3rd ACM\u2010SIAM Symposium on Discrete Algorithms, Orlando, FL, SIAM, Philadelphia, 1992, pp. 440\u2013452."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"A. Amir and G. Benson,\n                      Efficient two\u2010dimensional compressed matching\n                      , in Proc. Data Compression Conference, Snowbird, Utah, IEEE Computer Society Press, Los Alamitos, CA, 1992, pp. 279\u2013288.","DOI":"10.1109\/DCC.1992.227453"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"A. Amir, G. Benson, and M. Farach,\n                      Optimal parallel two dimensional text searching on a CREW PRAM\n                      , in Proc. 5th Annual Symposium on Parallel Algorithms and Architectures, ACM, New York, 1993, pp. 79\u201385.","DOI":"10.1145\/165231.165242"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792226321"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0860"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360855"},{"key":"R7","unstructured":"A. Amir and M. Farach,\n                      Efficient 2\u2010dimensional approximate matching of non\u2010rectangular figures\n                      , in Proc. 1st ACM\u2010SIAM Symposium on Discrete Algorithms, San Francisco, CA, SIAM, Philadelphia, 1990, pp. 212\u2013223."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90318-V"},{"key":"R9","unstructured":"A. Amir, G. M. Landau, and U. Vishkin,\n                      Efficient pattern matching with scaling\n                      , in Proc. 1st ACM\u2010SIAM Symposium on Discrete Algorithms, San Francisco, CA, SIAM, Philadelphia, 1990, pp. 344\u2013357."},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762122"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0207043"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90017-5"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/359842.359859"},{"key":"R14","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":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00012-3"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80031-0"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"Z. Galil and K. Park,\n                      Truly alphabet independent two\u2010dimensional pattern matching\n                      , in Proc. 33rd IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1992, pp. 247\u2013256.","DOI":"10.1109\/SFCS.1992.267767"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"M. Karpinski and W. Rytter,\n                      Alphabet independent optimal parallel search for 3\u2010dimensional patterns\n                      , in Proc. 5th Annual Symposium on Combinatorial Pattern Matching, Lecture Notes in Comput. Sci. 807, Springer\u2010Verlag, Berlin, 1994, pp. 125\u2013135.","DOI":"10.1007\/3-540-58094-8_11"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(87)90037-5"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322232"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"G. M. Landau and U. Vishkin,\n                      Efficient string matching in the presence of errors\n                      , in Proc. 26th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1985, pp. 126\u2013136.","DOI":"10.1109\/SFCS.1985.22"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90021-X"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"Mireille R\u00e9gnier, Ladan Rostami, A unifying look at d\u2010dimensional periodicities and space coverings, Lecture Notes in Comput. Sci., Vol. 684, Springer, Berlin, 1993, 215\u201322794j:68310","DOI":"10.1007\/BFb0029807"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/0217079"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80028-0"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/0220002"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"P. Weiner,\n                      Linear pattern matching algorithms\n                      , in Proc. 14th IEEE Symposium on Switching and Automata Theory, IEEE Computer Society Press, Los Alamitos, CA, 1973, pp. 1\u201311.","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539795298321","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:30Z","timestamp":1787336070000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795298321"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539795298321"],"URL":"https:\/\/doi.org\/10.1137\/s0097539795298321","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}