Dekel Tsur

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 x m substrings of an n x n text that p-match an m x m pattern. This models searching for color images with changing of color maps, for example. We present two algorithms that solve the twodimensional parameterized matching problem. The time complexities of our algorithms are O(n²log²m) and O(n² + m^2.5 polylog(m)). Our algorithms are faster than the O(n²mlog²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 x m substring of an n x n string. We show how to solve this problem in O(n²) time. This result may be of independent interest.