@inbook{eff2b4abf48647218b2cf6a72aafc09a,

title = "Function matching: Algorithms, applications, and a lower bound",

abstract = "We introduce a new matching criterion - function matching - that captures several different applications. The function matching problem has as its input a text T of length n over alphabet ΣT and a pattern P = P[1]P[2] ⋯ P[m] of length m over alphabet ΣP. We seek all text locations i for which, for some function f : ΣP > ΣT (f may also depend on i), the m-length substring that starts at i is equal to f(P[1])f(P[2])⋯f(P[m]). We give a randomized algorithm which, for any given constant k, solves the function matching problem in time O(n log n) with probability 1/nk of declaring a false positive. We give a deterministic algorithm whose time is O(n|ΣP|log m) and show that it is almost optimal in the newly formalized convolutions model. Finally, a variant of the third problem is solved by means of two-dimensional parameterized matching, for which we also give an efficient algorithm.",

keywords = "Color indexing, Function matching, Parameterized matching, Pattern matching, Protein folding, Register allocation",

author = "Amihood Amir and Yonatan Aumann and Richard Cole and Moshe Lewenstein and Ely Porat",

year = "2003",

doi = "10.1007/3-540-45061-0_72",

language = "English (US)",

isbn = "3540404937",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "929--942",

editor = "Baeten, {Jos C. M.} and Lenstra, {Jan Karel} and Joachim Parrow and Woeginger, {Gerhard J.}",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}