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 programs are considered "identical " even if variables are different. Strings, under this model, additionally have symbols from a variable set \Pi and occurrences of one string in the other up to a renaming of the variables are sought. In this paper we show that finding the occurrences of a m-length string in a n- length string under the parameterized pattern matching paradigm can be done in time O(n log ß), where ß = min(m; j\Pij); that is, independent of j\Sigmaj. Additionally, we show that in general this dependence on j\Pij is inherent to any algorithm for this problem in the comparison model -- that is, our algorithm is optimal