{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:21:14Z","timestamp":1759638074139,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,10,30]],"date-time":"2014-10-30T00:00:00Z","timestamp":1414627200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100004316","name":"International Business Machines Corporation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004316","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["981\/11"],"award-info":[{"award-number":["981\/11"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["IIS-0414763, CCF-0515127, CCF-0830516, and CCF-1217989"],"award-info":[{"award-number":["IIS-0414763, CCF-0515127, CCF-0830516, and CCF-1217989"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-0414763, CCF-0515127, CCF-0830516, and CCF-1217989"],"award-info":[{"award-number":["IIS-0414763, CCF-0515127, CCF-0830516, and CCF-1217989"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2014,11,17]]},"abstract":"<jats:p>\n            Two equal-length strings, or two equal-sized two-dimensional texts,\n            <jats:italic>parameterize match<\/jats:italic>\n            (\n            <jats:italic>p-match<\/jats:italic>\n            ) if there is a one-one mapping (relative to the alphabet) of their characters.\n            <jats:italic>Two-dimensional parameterized matching<\/jats:italic>\n            is the task of finding all\n            <jats:italic>m<\/jats:italic>\n            \u00d7\n            <jats:italic>m<\/jats:italic>\n            substrings of an\n            <jats:italic>n<\/jats:italic>\n            \u00d7\n            <jats:italic>n<\/jats:italic>\n            text that p-match an\n            <jats:italic>m<\/jats:italic>\n            \u00d7\n            <jats:italic>m<\/jats:italic>\n            pattern. This models searching for color images with changing of color maps, for example. We present two algorithms that solve the two-dimensional parameterized matching problem. The time complexities of our algorithms are\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>m<\/jats:italic>\n            ) and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            +\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>2.5<\/jats:sup>\n            polylog(\n            <jats:italic>m<\/jats:italic>\n            )). Our algorithms are faster than the\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>m<\/jats:italic>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>m<\/jats:italic>\n            log log\n            <jats:italic>m<\/jats:italic>\n            ) time algorithm for this problem of Amir et al. [2006].\n          <\/jats:p>\n          <jats:p>\n            A key step in both of our algorithms is to count the number of distinct characters in every\n            <jats:italic>m<\/jats:italic>\n            \u00d7\n            <jats:italic>m<\/jats:italic>\n            substring of an\n            <jats:italic>n<\/jats:italic>\n            \u00d7\n            <jats:italic>n<\/jats:italic>\n            string. We show how to solve this problem in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) time. This result may be of independent interest.\n          <\/jats:p>","DOI":"10.1145\/2650220","type":"journal-article","created":{"date-parts":[[2014,10,31]],"date-time":"2014-10-31T19:28:54Z","timestamp":1414783734000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Two-Dimensional Parameterized Matching"],"prefix":"10.1145","volume":"11","author":[{"given":"Richard","family":"Cole","sequence":"first","affiliation":[{"name":"New York University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carmit","family":"Hazay","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moshe","family":"Lewenstein","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dekel","family":"Tsur","sequence":"additional","affiliation":[{"name":"University of Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,10,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940874"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702424496"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792226321"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2003.12.001"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90086-8"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2006.03.014"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921659.1921670"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215051"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0003"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793246707"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.08.002"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509992"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701424465"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1038"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273340.1273345"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796302"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00130487"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/646239.683518"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220002"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2650220","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2650220","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:11:54Z","timestamp":1750227114000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2650220"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,30]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,11,17]]}},"alternative-id":["10.1145\/2650220"],"URL":"https:\/\/doi.org\/10.1145\/2650220","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2014,10,30]]},"assertion":[{"value":"2012-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}