Two equal-length strings, or two equal-sized two-dimensional texts,  parameterize match  ( p-match ) if there is a one-one mapping (relative to the alphabet) of their characters.  Two-dimensional parameterized matching  is the task of finding all  m  ×  m  substrings of an  n  ×  n  text that p-match an  m  ×  m  pattern. This models searching for color images with changing of color maps, for example. We present two algorithms that solve the two-dimensional parameterized matching problem. The time complexities of our algorithms are  O ( n  2  log 2   m ) and  O ( n  2  p  m  2.5  polylog( m )). Our algorithms are faster than the  O ( n  2  m  log 2   m  log log  m ) time algorithm for this problem of Amir et al. [2006].   A key step in both of our algorithms is to count the number of distinct characters in every  m  ×  m  substring of an  n  ×  n  string. We show how to solve this problem in  O ( n  2 ) time. This result may be of independent interest.
['Richard Cole', 'Carmit Hazay', 'Moshe Lewenstein', 'Dekel Tsur']
Two-Dimensional Parameterized Matching