Function matching: Algorithms, applications, and a lower bound

Amihood Amir, Yonatan Aumann, Richard Cole, Moshe Lewenstein, Ely Porat

Research output: Chapter in Book/Report/Conference proceedingChapter

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.

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsJos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, Gerhard J. Woeginger
PublisherSpringer Verlag
Pages929-942
Number of pages14
ISBN (Print)3540404937, 9783540404934
DOIs
StatePublished - 2003

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2719
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • Color indexing
  • Function matching
  • Parameterized matching
  • Pattern matching
  • Protein folding
  • Register allocation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Function matching: Algorithms, applications, and a lower bound'. Together they form a unique fingerprint.

Cite this