Language: C++

/*
 * 2D string matching
 * Approach: 2D fingerprinting
 */

#include <iostream>
#include <string>
#include <vector>
using namespace std;
using ull = unsigned long long;
constexpr ull MODULUS = 1e9 + 9;
constexpr ull PRIME = 47;

int ValueOf(char ch) {
  if ('0' <= ch && ch <= '9')
    return ch - '0';
  return 10 + ch - 'a';
}

void Match(const vector<string> &T, const vector<string> &P) {
  int N = T.size(), M = T[0].size(), n = P.size(), m = P[0].size();
  // Precompute:
  // 1. h(P) -- treating rectangular ranges as 1D vectors in row-major order
  // 2. h(p^{km}) for k=1,...,n-1
  // 2a. h(p^{m-1})
  // 3. h(T[i][j..(j+m-1)]) for i=0,...,n-1, j=0,...,M-m

  ull pattern_hash = 0;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      pattern_hash =
          (((pattern_hash * PRIME) % MODULUS) + ValueOf(P[i][j])) % MODULUS;

  int current_power = 1;
  ull hash_pmminus1 = PRIME;
  for (; current_power < m - 1; current_power <<= 1)
    hash_pmminus1 = (hash_pmminus1 * hash_pmminus1) % MODULUS;
  for (; current_power < m - 1; ++current_power)
    hash_pmminus1 = (hash_pmminus1 * PRIME) % MODULUS;
  ull hash_pm = (hash_pmminus1 * PRIME) % MODULUS;

  vector<ull> hash_ppowermtimes(n); // ith element stores h(p^{mi})
  hash_ppowermtimes[0] = 1;
  hash_ppowermtimes[1] = hash_pm;
  for (int i = 2; i < n; ++i) {
    // h(p^{mi}) = h(p^m)h(p^{m(i-1)})
    hash_ppowermtimes[i] = (hash_pm * hash_ppowermtimes[i - 1]) % MODULUS;
  }

  vector<vector<ull>> H(N, vector<ull>(M));
  for (int i = 0; i < N; ++i) {
    ull segment_hash = 0;
    for (int j = 0; j < m; ++j)
      segment_hash =
          (((segment_hash * PRIME) % MODULUS) + ValueOf(T[i][j])) % MODULUS;
    H[i][0] = segment_hash;
    for (int j = 1; j <= M - m; ++j) {
      segment_hash =
          (segment_hash - (hash_pmminus1 * ValueOf(T[i][j - 1]) % MODULUS)) %
          MODULUS; // remove earliest element
      segment_hash = (segment_hash * PRIME) % MODULUS; // shift left
      segment_hash =
          (segment_hash + ValueOf(T[i][j + m - 1])) % MODULUS; // append
      H[i][j] = segment_hash;
    }
  }

  // Traverse and report
  vector<pair<int, int>> matches;
  for (int j = 0; j <= M - m; ++j) {
    ull text_hash = 0;
    for (int i = 0; i < n; ++i)
      text_hash = (((text_hash * hash_pm) % MODULUS) + H[i][j]) % MODULUS;
    if (text_hash == pattern_hash)
      matches.emplace_back(0, j);
    for (int i = 1; i <= N - n; ++i) {
      text_hash =
          (text_hash - ((hash_ppowermtimes[n - 1]) * H[i - 1][j] % MODULUS)) %
          MODULUS;                                 // remove top row
      text_hash = (text_hash * hash_pm) % MODULUS; // shift up
      text_hash += H[i + n - 1][j];                // append
      if (text_hash == pattern_hash)
        matches.emplace_back(i, j);
    }
  }
  sort(begin(matches), end(matches));
  for (auto &p : matches)
    cout << p.first << " " << p.second << endl;
}

int main() {
  int n, m;
  cin >> n >> m;
  vector<string> T, P;
  string cur;
  while (n--) {
    cin >> cur;
    T.push_back(cur);
  }
  cin >> n >> m;
  while (n--) {
    cin >> cur;
    P.push_back(cur);
  }
  Match(T, P);
}


Compiler output:
a.cc: In function 'void Match(const std::vector<std::__cxx11::basic_string<char> >&, const std::vector<std::__cxx11::basic_string<char> >&)':
a.cc:86:3: error: 'sort' was not declared in this scope; did you mean 'short'?
   86 |   sort(begin(matches), end(matches));
      |   ^~~~
      |   short