Matching Patterns with Variables Under Edit Distance

Paweł Gawrychowski, Florin Manea, Stefan Siemer

A pattern $\alpha$ is a string of variables and terminal letters. We say that $\alpha$ matches a word $w$, consisting only of terminal letters, if $w$ can be obtained by replacing the variab…