{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:33:53Z","timestamp":1787340833895,"version":"build-2736575974"},"reference-count":26,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1994,4]]},"abstract":"<jats:p>There are many solutions to the string matching problem that are strictly linear in the input size and independent of alphabet size. Furthermore, the model of computation for these algorithms is very weak: they allow only simple arithmetic and comparisons of equality between characters of the input. In contrast, algorithms for two-dimensional matching have needed stronger models of computation, most notably assuming a totally ordered alphabet. The fastest algorithms for two-dimensional matching have therefore had a logarithmic dependence on the alphabet size. In the worst case, this gives an algorithm that runs in $O(n^2 \\log m)$ with $O(m^2 \\log m)$ preprocessing.<\/jats:p>\n                  <jats:p>The authors show an algorithm for two-dimensional matching with an $O(n^2 )$ text-scanning phase. Furthermore, the text scan requires no special assumptions about the alphabet, i.e., it runs on the same model as the standard linear-time string-matching algorithm. The pattern preprocessing requires an ordered alphabet and runs with the same alphabet dependency as the previously known algorithms.<\/jats:p>","DOI":"10.1137\/s0097539792226321","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:39:46Z","timestamp":1109227186000},"page":"313-323","source":"Crossref","is-referenced-by-count":67,"title":["An Alphabet Independent Approach to Two-Dimensional Pattern Matching"],"prefix":"10.1137","volume":"23","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"}]},{"given":"Martin","family":"Farach","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360855"},{"key":"R2","unstructured":"A. Amir, G. Benson,  Two-dimensional periodicity and its application,  Proc. of 3rd Symposium on Discrete Algorithms, Orlando, FL,  1992,  440\u2013452 0829.68062"},{"key":"R3","unstructured":"A. Amir, G. Benson, M. Farach,  The truth, the whole truth and nothing but the truth: Alphabet independent  2-\n                      d\n                      witness table construction, Tech. Rep., GIT-CC-92-51,  1992, Georgia Tech"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90206-B"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90318-V"},{"key":"R6","unstructured":"A. Amir, G. Landau, U. Vishkin,  Efficient pattern matching with scaling,  Proc. of First Symposium on Discrete Algorithms, San Francisco, CA,  1990,  344\u2013357 0800.68490"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"R. Baeza-Yates, M. R\u00e9gnier,  Fast algorithms for two dimensional and multiple pattern matching,  Proc. of 2nd Annual Scandinavian Workshop in Algorithmic Theory, SWAT '90,  1990","DOI":"10.1007\/3-540-52846-6_102"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0207043"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90017-5"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/359842.359859"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-82456-2_7"},{"key":"R12","volume-title":"Complexity of computation (Proc. SIAM-AMS Appl. Math. Sympos., New York, 1973)","author":"Fischer M.","year":"1974"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-82456-2_1"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Z. Galil, K. Park,  Truly alphabet-independent two-dimensional pattern matching,  Proc. 33rd IEEE FOCS,  1992","DOI":"10.1109\/SFCS.1992.267767"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90002-8"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"R. Karp, R. Miller, A. Rosenberg,  Rapid identification of repeated patterns in strings, arrays and trees,  Symposium on the Theory of Computing, Vol. 4,  1972,  125\u2013136 0354.68119","DOI":"10.1145\/800152.804905"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1147\/rd.312.0249"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"G. Landau, U. Vishkin,  Efficient string matching in the presence of errors,  Proc. 26th IEEE FOCS,  1985,  126\u2013126","DOI":"10.1109\/SFCS.1985.22"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90021-X"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321946"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-597302-1.50010-4"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/0220002"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"Peter Weiner,  Linear pattern matching algorithms,  14th Annual IEEE Symposium on Switching and Automata Theory (Univ. Iowa, Iowa City, Iowa, 1973), IEEE Comput. Soc., Northridge, Calif.,  1973,  1\u201311 55:13898","DOI":"10.1109\/SWAT.1973.13"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1145\/66451.66459"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539792226321","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:51:11Z","timestamp":1787338271000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539792226321"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,4]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1994,4]]}},"alternative-id":["10.1137\/S0097539792226321"],"URL":"https:\/\/doi.org\/10.1137\/s0097539792226321","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,4]]}}}