  We consider a class of pattern matching problems where a normalising
transformation is applied at every alignment. Normalised pattern matching plays
a key role in fields as diverse as image processing and musical information
processing where application specific transformations are often applied to the
input. By considering the class of polynomial transformations of the input, we
provide fast algorithms and the first lower bounds for both new and old
problems. Given a pattern of length m and a longer text of length n where both
are assumed to contain integer values only, we first show O(n log m) time
algorithms for pattern matching under linear transformations even when wildcard
symbols can occur in the input. We then show how to extend the technique to
polynomial transformations of arbitrary degree. Next we consider the problem of
finding the minimum Hamming distance under polynomial transformation. We show
that, for any epsilon>0, there cannot exist an O(n m^(1-epsilon)) time
algorithm for additive and linear transformations conditional on the hardness
of the classic 3SUM problem. Finally, we consider a version of the Hamming
distance problem under additive transformations with a bound k on the maximum
distance that need be reported. We give a deterministic O(nk log k) time
solution which we then improve by careful use of randomisation to O(n sqrt(k
log k) log n) time for sufficiently small k. Our randomised solution outputs
the correct answer at every position with high probability.
