Faster two-dimensional pattern matching with k mismatches

The classical pattern matching asks for locating all occurrences of one string, called the pattern, in another, called the text, where a string is simply a sequence of characters. Due to the potential practical applications, it is desirable to seek approximate occurrences, for example by bounding the number of mismatches. This problem has been extensively studied, and by now we have a good understanding of the best possible time complexity as a function of n (length of the text), m (length of the pattern), and k (number of mismatches). In particular, we know that for , we can achieve quasi-linear time complexity [Gawrychowski and Uznański, ICALP 2018].