ALPHABET DEPENDENCE IN PARAMETERIZED MATCHING

The classical pattern matching paradigm is that of seeking occurrences of one string in another, where both strings are drawn from an alphabet set Sigma. 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 Sigma, strings under this model have additional symbols from a variable set II and occurrences of one string in the other are sought, where renaming of the variables from II is allowed in a match. In this paper we provide an algorithm to find air occurrences 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 pi), where pi = min(m, \II\), independent of \Sigma\. Our algorithm is optimal since we show that this dependence on \II\ is inherent to any algorithm for this problem in the comparison model.