  A pattern p (i.e., a string of variables and terminals) matches a word w, if
w can be obtained by uniformly replacing the variables of p by terminal words.
The respective matching problem, i.e., deciding whether or not a given pattern
matches a given word, is generally NP-complete, but can be solved in
polynomial-time for classes of patterns with restricted structure. In this
paper we overview a series of recent results related to efficient matching for
patterns with variables, as well as a series of extensions of this problem.
