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 language | English (US) |
---|---|
Pages (from-to) | 111-115 |
Number of pages | 5 |
Journal | Information Processing Letters |
Volume | 49 |
Issue number | 3 |
DOIs | |
State | Published - 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