Two-Dimensional Parameterized Matching
Richard J. Cole, Carmit Hazay, Moshe Lewenstein, Dekel Tsur · ACM Transactions on Algorithms · 2014
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 + 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.