Cod sursă (job #546883)

#include <fstream>

using namespace std;

ifstream fin("fotografie.in");
ofstream fout("fotografie.out");

#define MAX 10002
#define mod 46103

char a[MAX][MAX], b[MAX][MAX];
int nr[MAX], mx, my, mz, p, q, m, n, sm, val;

void ok(int x, int y) {
  for (int i = x; i > x - p; --i)
    for (int j = y; j > y - q; --j)
      if (a[i][j] != b[i - (x - p + 1)][j - (y - q + 1)])
        return;
  fout << x - p + 1 << ' ' << y - q + 1 << '\n';
}

int main() {
  fin >> n >> m;
  for (int i = 0; i < n; ++i)
    fin >> a[i];

  fin >> p >> q;
  for (int i = 0; i < p; ++i)
    fin >> b[i];

  for (int j = 0; j < q; ++j)
    for (int i = 0; i < p; ++i)
      sm = (sm * 26 + (b[i][j] - 'a')) % mod;

  mx = 1;
  my = 1;
  mz = 1;
  for (int i = 1; i < p; ++i)
    mx = (mx * 26) % mod;

  mz = (mx * 26) % mod;
  for (int i = 1; i < q; ++i)
    my = (my * mz) % mod;

  for (int j = 0; j < m; ++j)
    for (int i = 0; i < p - 1; ++i)
      nr[j] = (nr[j] * 26 + (a[i][j] - 'a')) % mod;

  for (int i = p - 1; i < n; ++i) {
    for (int j = 0; j < m; ++j)
      nr[j] = (nr[j] * 26 + (a[i][j] - 'a')) % mod;

    val = 0;
    for (int j = 0; j < q - 1; ++j)
      val = (val * mz + nr[j]) % mod;

    for (int j = q - 1; j < m; ++j) {
      val = (val * mz + nr[j]) % mod;
      if (val == sm)
        ok(i, j);

      val = ((val - my * nr[j - q + 1]) % mod);
      if (val < 0)
        val += mod;
    }

    for (int j = 0; j < m; ++j) {
      nr[j] = (nr[j] - mx * (a[i - p + 1][j] - 'a')) % mod;
      if (nr[j] < mod)
        nr[j] += mod;
    }
  }

  return 0;
}