Cod sursă (job #546941)

#include <bits/stdc++.h>

using namespace std;

typedef unsigned ull;

const int BASE1 = 137;
const int BASE2 = 29989;
const int MOD = 1e9 + 7;

const int Nmax = 1000;

ull base1[Nmax + 1], base2[Nmax + 1];
ull hashes[Nmax + 1];
char S[Nmax + 1][Nmax + 1], T[Nmax + 1][Nmax + 1];
int N, M;
int P, Q;

void init() {
  base1[0] = base2[0] = 1;

  for (int i = 1; i <= Nmax; ++i) {
    base1[i] = base1[i - 1] * BASE1;
    base2[i] = base2[i - 1] * BASE2;
  }
}

void Rabin_Karp() {
  ull hashPattern, hashText;

  for (int j = 1; j <= M; ++j)
    for (int i = 1; i <= P; ++i)
      hashes[j] = hashes[j] * BASE1 + T[i][j];

  hashPattern = 0;

  for (int j = 1; j <= Q; ++j) {
    ull code = 0;

    for (int i = 1; i <= P; ++i)
      code = code * BASE1 + S[i][j];

    hashPattern = hashPattern * BASE2 + code;
  }

  ofstream out("fotografie.out");

  for (int i = 1; i + P - 1 <= N; ++i) {
    hashText = 0;

    for (int j = 1; j <= Q; ++j)
      hashText = hashText * BASE2 + hashes[j];

    if (hashText == hashPattern)
      out << i - 1 << " " << 0 << "\n";

    for (int j = Q + 1; j <= M; ++j) {
      hashText = (hashText * BASE2 + hashes[j] - base2[Q] * hashes[j - Q]);

      if (hashText == hashPattern)
        out << i - 1 << " " << j - Q << "\n";
    }

    for (int j = 1; j <= M; ++j)
      hashes[j] = (hashes[j] * BASE1 + T[i + P][j] - base1[P] * T[i][j]);
  }
}

int main() {
  ifstream in("fotografie.in");

  ios_base::sync_with_stdio(false);

  in >> N >> M;

  for (int i = 1; i <= N; ++i)
    in >> (T[i] + 1);

  in >> P >> Q;

  for (int i = 1; i <= P; ++i)
    in >> (S[i] + 1);

  init();
  Rabin_Karp();

  return 0;
}