Alphabet dependence in parameterized matching

Amihood Amir, Martin Farach, S. Muthukrishnan

Research output: Contribution to journalArticlepeer-review

86 Scopus citations


The classical pattern matching paradigm is that of seeking occurences of one string in another, where both strings are drawn from an alphabet set Σ. A recently introduced model is that of parameterized pattern matching. The main motivation for this scheme lies in software maintenance where program fragments are considered "identical" even if variables names are different. Besides the fixed symbols from Σ, strings under this model have additional symbols from a variable set Π and occurences of one string in the other are sought, where renaming of the variables from Π is allowed in a match. In this paper we provide an algorithm to find all occurences of a pattern string of length m in a text string of length n under the parameterized pattern matching model. Our algorithm takes time O(n log π), where π = min(m, |Π|), independent of |Σ|. Our algorithm is optimal since weshow that this dependence on |Π| is inherent to any algorithm for this problem in the comparison model.

Original languageEnglish (US)
Pages (from-to)111-115
Number of pages5
JournalInformation Processing Letters
Issue number3
StatePublished - Feb 11 1994

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


  • Algorithms
  • Analysis of algorithms
  • Parameterized string matching
  • Software maintenance
  • String matching

Fingerprint Dive into the research topics of 'Alphabet dependence in parameterized matching'. Together they form a unique fingerprint.

Cite this