Alphabet Dependence in Parameterized Matching

Show simple item record Amir, Amihood en_US Farach-Colton, Martin Muthukrishnan, S. 2005-06-17T18:04:06Z 2005-06-17T18:04:06Z 1993 en_US
dc.description.abstract The classical pattern matching paradigm is that of seeking occurrences 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 programs are considered "identical" even if variables are different. Strings, under this model, additionally have symbols from a variable set Π 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, ∣Π∣); that is , independent of ∣∑∣. Additionally, we show that in general this dependence on ∣Π∣ is inherent to any algorithm for this problem in the comparison model – that is, our algorithm is optimal. en_US
dc.format.extent 147501 bytes
dc.format.mimetype application/pdf
dc.language.iso en_US
dc.publisher Georgia Institute of Technology en_US
dc.relation.ispartofseries CC Technical Report; GIT-CC-93-44 en_US
dc.subject Parameterized matching
dc.subject Strings
dc.subject Alphabet sets
dc.subject Comparison models
dc.subject Standard string matching
dc.title Alphabet Dependence in Parameterized Matching en_US
dc.type Technical Report eng_US

Files in this item

Files Size Format View
GIT-CC-93-44.pdf 144.0Kb PDF View/ Open

This item appears in the following Collection(s)

Show simple item record