{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T23:28:27Z","timestamp":1769297307554,"version":"3.49.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2007,8,1]],"date-time":"2007-08-01T00:00:00Z","timestamp":1185926400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2007,8]]},"abstract":"<jats:p>\n            Two equal length strings\n            <jats:italic>s<\/jats:italic>\n            and\n            <jats:italic>s<\/jats:italic>\n            \u2032, over alphabets \u03a3\n            <jats:sub>\n              <jats:italic>s<\/jats:italic>\n            <\/jats:sub>\n            and \u03a3\n            <jats:sub>\n              <jats:italic>s<\/jats:italic>\n            <\/jats:sub>\n            \u2032,\n            <jats:italic>parameterize match<\/jats:italic>\n            if there exists a bijection \u03c0 : \u03a3\n            <jats:sub>\n              <jats:italic>s<\/jats:italic>\n            <\/jats:sub>\n            \u2192 \u03a3\n            <jats:sub>\n              <jats:italic>s<\/jats:italic>\n            <\/jats:sub>\n            \u2032 such that \u03c0 (\n            <jats:italic>s<\/jats:italic>\n            ) =\n            <jats:italic>s<\/jats:italic>\n            \u2032, where \u03c0 (\n            <jats:italic>s<\/jats:italic>\n            ) is the renaming of each character of\n            <jats:italic>s<\/jats:italic>\n            via \u03c0.\n            <jats:italic>Parameterized matching<\/jats:italic>\n            is the problem of finding all parameterized matches of a pattern string\n            <jats:italic>p<\/jats:italic>\n            in a text\n            <jats:italic>t<\/jats:italic>\n            , and\n            <jats:italic>approximate parameterized matching<\/jats:italic>\n            is the problem of finding at each location a bijection \u03c0 that maximizes the number of characters that are mapped from\n            <jats:italic>p<\/jats:italic>\n            to the appropriate |\n            <jats:italic>p<\/jats:italic>\n            |-length substring of\n            <jats:italic>t<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>Parameterized matching was introduced as a model for software duplication detection in software maintenance systems and also has applications in image processing and computational biology. For example, approximate parameterized matching models image searching with variable color maps in the presence of errors.<\/jats:p>\n          <jats:p>\n            We consider the problem for which an error threshold,\n            <jats:italic>k<\/jats:italic>\n            , is given, and the goal is to find all locations in\n            <jats:italic>t<\/jats:italic>\n            for which there exists a bijection \u03c0 which maps\n            <jats:italic>p<\/jats:italic>\n            into the appropriate |\n            <jats:italic>p<\/jats:italic>\n            |-length substring of\n            <jats:italic>t<\/jats:italic>\n            with at most\n            <jats:italic>k<\/jats:italic>\n            mismatched mapped elements. Our main result is an algorithm for this problem with\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>nk<\/jats:italic>\n            <jats:sup>1.5<\/jats:sup>\n            +\n            <jats:italic>mk<\/jats:italic>\n            log\n            <jats:italic>m<\/jats:italic>\n            ) time complexity, where\n            <jats:italic>m<\/jats:italic>\n            = |\n            <jats:italic>p<\/jats:italic>\n            | and\n            <jats:italic>n<\/jats:italic>\n            =|\n            <jats:italic>t<\/jats:italic>\n            |. We also show that when |\n            <jats:italic>p<\/jats:italic>\n            | = |\n            <jats:italic>t<\/jats:italic>\n            | =\n            <jats:italic>m<\/jats:italic>\n            , the problem is equivalent to the maximum matching problem on graphs, yielding a\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            +\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>1.5<\/jats:sup>\n            ) solution.\n          <\/jats:p>","DOI":"10.1145\/1273340.1273345","type":"journal-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T13:44:55Z","timestamp":1189777495000},"page":"29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":33,"title":["Approximate parameterized matching"],"prefix":"10.1145","volume":"3","author":[{"given":"Carmit","family":"Hazay","sequence":"first","affiliation":[{"name":"Bar-Ilan University, Ramat Gan, Israel"}]},{"given":"Moshe","family":"Lewenstein","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Ramat Gan, Israel"}]},{"given":"Dina","family":"Sokol","sequence":"additional","affiliation":[{"name":"Brooklyn College of the City University of New York"}]}],"member":"320","published-online":{"date-parts":[[2007,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). 929--942","author":"Amir A.","unstructured":"Amir , A. , Aumann , Y. , Cole , R. , Lewenstein , M. , and Porat , E . 2003. Function matching: Algorithms, applications, and a lower bound . In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). 929--942 . Amir, A., Aumann, Y., Cole, R., Lewenstein, M., and Porat, E. 2003. Function matching: Algorithms, applications, and a lower bound. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). 929--942."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792226321"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA). 400--401","author":"Amir A.","unstructured":"Amir , A. , Church , K. W. , and Dar , E . 2002. Separable attributes: a technique for solving the sub matrices character count problem . In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA). 400--401 . Amir, A., Church, K. W., and Dar, E. 2002. Separable attributes: a technique for solving the sub matrices character count problem. In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA). 400--401."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90086-8"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2006.03.014"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215882"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167115"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0003"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793246707"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 854--855","author":"Baker B. S.","year":"1999","unstructured":"Baker , B. S. 1999 . Parameterized diff . In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 854--855 . Baker, B. S. 1999. Parameterized diff. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 854--855."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/359842.359859"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335352"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90039-X"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218069"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/8307.8309"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 12th Annual European Symposium on Algorithms (ESA), S. Albers and T. Radzik, Eds. Lecture Notes in Computer Science","volume":"3221","author":"Hazay C.","unstructured":"Hazay , C. , Lewenstein , M. , and Sokol , D . 2004. Approximate parameterized matching . In Proceedings of the 12th Annual European Symposium on Algorithms (ESA), S. Albers and T. Radzik, Eds. Lecture Notes in Computer Science , vol. 3221 . Springer, 414--425. Hazay, C., Lewenstein, M., and Sokol, D. 2004. Approximate parameterized matching. In Proceedings of the 12th Annual European Symposium on Algorithms (ESA), S. Albers and T. Radzik, Eds. Lecture Notes in Computer Science, vol. 3221. Springer, 414--425."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799361208"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796302"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/11534.11541"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90045-1"},{"key":"e_1_2_1_24_1","first-page":"707","article-title":"Binary codes capable of correcting, deletions, insertions and reversals","volume":"10","author":"Levenshtein V. I.","year":"1966","unstructured":"Levenshtein , V. I. 1966 . Binary codes capable of correcting, deletions, insertions and reversals . Soviet Phys. Dokl. 10 , 707 -- 710 . Levenshtein, V. I. 1966. Binary codes capable of correcting, deletions, insertions and reversals. Soviet Phys. Dokl. 10, 707--710.","journal-title":"Soviet Phys. Dokl."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217079"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00130487"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1273340.1273345","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1273340.1273345","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:57:55Z","timestamp":1750258675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1273340.1273345"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,8]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,8]]}},"alternative-id":["10.1145\/1273340.1273345"],"URL":"https:\/\/doi.org\/10.1145\/1273340.1273345","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,8]]},"assertion":[{"value":"2007-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}