{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T09:07:55Z","timestamp":1787389675994,"version":"build-2736575974"},"reference-count":32,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2006,1]]},"abstract":"<jats:p>We present problems in the following three application areas: identifying similar codes in which global register reallocation and spill code minimization were done (programming languages); protein threading (computational biology); and searching for color icons under different color maps (image processing).<\/jats:p>\n                  <jats:p>We introduce a new search model called function matching that enables us to solve the above problems. The function matching problem has as its input a text T of length n over alphabet $\\Sigma_T$ and a pattern $P = P[1] P[2] \\cdots P[m]$ of length m over alphabet $\\Sigma_P$. We seek all text locations i, where the m-length substring that starts at i is equal to $f(P[1]) f(P[2]) \\cdots f(P[m])$, for some function $f: \\Sigma_P \\rightarrow \\Sigma_T$.<\/jats:p>\n                  <jats:p>We give a randomized algorithm that solves the function matching problem in time $O(n\\log n)$ with probability ${1\\over n}$ of declaring a false positive. We give a deterministic algorithm whose time is $O(n |\\Sigma_P| \\log m)$ and show that it is optimal in the convolutions model. We use function matching to efficiently solve the problem of two-dimensional parameterized matching.<\/jats:p>","DOI":"10.1137\/s0097539702424496","type":"journal-article","created":{"date-parts":[[2006,3,27]],"date-time":"2006-03-27T21:00:21Z","timestamp":1143493221000},"page":"1007-1022","source":"Crossref","is-referenced-by-count":14,"title":["Function Matching"],"prefix":"10.1137","volume":"35","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yonatan","family":"Aumann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moshe","family":"Lewenstein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ely","family":"Porat","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/0216067"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1120"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792226321"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2003.12.001"},{"key":"R5","unstructured":"Amihood Amir, Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat, Overlap matching, SIAM, Philadelphia, PA, 2001, 279\u2013288MR1958420"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1047"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90086-8"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90318-V"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780195113679.001.0001"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215882"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"B. S. Baker,\n                      A theory of parameterized pattern matching: Algorithms and applications\n                      , in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, ACM, New York, 1993, pp. 71\u201380.","DOI":"10.1145\/167088.167115"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1126\/science.1853201"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/359842.359859"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"M. Chen, Joel Seiferas, Efficient and elegant subword\u2010tree construction, NATO Adv. Sci. Inst. Ser. F Comput. Systems Sci., Vol. 12, Springer, Berlin, 1985, 97\u201310787e:68034","DOI":"10.1007\/978-3-642-82456-2_7"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Richard Cole, Ramesh Hariharan, Tree pattern matching and subset matching in randomized O(nlog3m) time, ACM, New York, 1999, 66\u201375MR1715625","DOI":"10.1145\/258533.258553"},{"key":"R16","unstructured":"Richard Cole, Ramesh Hariharan, Piotr Indyk, Tree pattern matching and subset matching in deterministic O(nlog3n)\u2010time, ACM, New York, 1999, 245\u2013254MR1739952"},{"key":"R17","unstructured":"T. H. Cormen, C. E. Leiserson, and R. L. Rivest,\n                      Introduction to Algorithms\n                      , MIT Press, Cambridge, MA; McGraw\u2010Hill, New York, 1990."},{"key":"R18","volume-title":"Text algorithms","author":"Crochemore Maxime","year":"1994"},{"key":"R19","unstructured":"Michael Fischer, Michael Paterson, String\u2010matching and other products, Amer. Math. Soc., Providence, R. I., 1974, 0\u20130, 113\u2013125. SIAM\u2010AMS Proc., Vol. VII53:4612"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"R21","first-page":"1","volume":"63","author":"Fredriksson Kimmo","year":"2004","journal-title":"Fund. Inform."},{"key":"R22","doi-asserted-by":"crossref","unstructured":"W. C. Kreahling and C. Norris,\n                      Profile assisted register allocation\n                      , in Proceedings of the ACM Symposium on Applied Computing (SAC), ACM, New York, 2000, pp. 774\u2013781.","DOI":"10.1145\/338407.338562"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1145\/353926.353929"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"K. Merz, Jr., and S. M. Le Grand,\n                      The Protein Folding Problem and Tertiary Structure Prediction\n                      , Birkh\u00e4user Boston, Boston, MA, 1994.","DOI":"10.1007\/978-1-4684-6831-1"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"S. Muthukrishnan, New results and open problems related to non\u2010standard stringology, Lecture Notes in Comput. Sci., Vol. 937, Springer, Berlin, 1995, 298\u201331798h:68098","DOI":"10.1007\/3-540-60044-2_50"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"S. Muthukrishnan and K. Palem,\n                      Nonstandard stringology: Algorithms and complexity\n                      , in Proceedings of the 26th Annual Symposium on the Theory of Computing, ACM, New York, 1994, pp. 770\u2013779.","DOI":"10.1145\/195058.195457"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1007\/BF00130487"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80028-0"},{"key":"R29","doi-asserted-by":"publisher","unstructured":"Richard Cole, Ramesh Hariharan, Piotr Indyk, Tree pattern matching and subset matching in deterministic O(nlog3n)\u2010time, ACM, New York, 1999, 245\u201325410.1137\/0220002MR1739952","DOI":"10.1137\/0220002"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"P. Weiner,\n                      Linear pattern matching algorithm\n                      , in Proceedings of the 14th Annual IEEE Symposium on Switching and Automata Theory, IEEE, Piscataway, NJ, 1973, pp. 1\u201311.","DOI":"10.1109\/SWAT.1973.13"},{"key":"R31","unstructured":"J. Yadgari, A. Amir, and R. Unger,\n                      Genetic algorithms for protein threading\n                      , in Proceedings of the 6th Annual International Conference on Intelligent Systems for Molecular Biology (ISMB 98), J. Glasgow, T. Littlejohn, F. Major, R. Lathrop, D. Sankoff, and C. Sensen, eds., AAAI Press, Menlo Park, CA, 1998, pp. 193\u2013202."},{"key":"R32","volume-title":"Conference Record of the Eleventh Annual ACM Symposium on Theory of Computing","year":"1979"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539702424496","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:17:12Z","timestamp":1787336232000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539702424496"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1137\/S0097539702424496"],"URL":"https:\/\/doi.org\/10.1137\/s0097539702424496","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}