Alphabet dependence in parameterized matching

Amihood Amir, Martin Farach, S. Muthukrishnan

    Research output: Contribution to journalArticlepeer-review

    Abstract

    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
    Volume49
    Issue number3
    DOIs
    StatePublished - Feb 11 1994

    Keywords

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

    ASJC Scopus subject areas

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

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

    Cite this