Cod sursă (job #547378)

#include <fstream>
using namespace std;
typedef unsigned u;

ofstream fout("fotografie.out");
ifstream fin("fotografie.in");
u base1[1001], base2[1001], hashes[1001];
char s[1001][1001], t[1001][1001];
int n, m, p, q;

int main() {
  fin >> n >> m;
  for (int i = 1; i <= n; i++)
    fin >> (t[i] + 1);
  fin >> p >> q;
  for (int i = 1; i <= p; i++)
    fin >> (s[i] + 1);
  base1[0] = base2[0] = 1;
  for (int i = 1; i <= 1000; i++) {
    base1[i] = base1[i - 1] * 137;
    base2[i] = base2[i - 1] * 29989;
  }
  u hashpattern = 0;
  for (int j = 1; j <= m; j++)
    for (int i = 1; i <= p; i++)
      hashes[j] = hashes[j] * 137 + t[i][j];
  for (int j = 1; j <= q; j++) {
    u code = 0;
    for (int i = 1; i <= p; i++)
      code = code * 137 + s[i][j];
    hashpattern = hashpattern * 29989 + code;
  }
  for (int i = 1; i + p - 1 <= n; i++) {
    u hashtext = 0;
    for (int j = 1; j <= q; j++)
      hashtext = hashtext * 29989 + hashes[j];
    if (hashtext == hashpattern)
      fout << i - 1 << ' ' << 0 << '\n';
    for (int j = q + 1; j <= m; j++) {
      hashtext = (hashtext * 29989 + hashes[j] - base2[q] * hashes[j - q]);
      if (hashtext == hashpattern)
        fout << i - 1 << ' ' << j - q << '\n';
    }
    for (int j = 1; j <= m; j++)
      hashes[j] = (hashes[j] * 137 + t[i + p][j] - base1[p] * t[i][j]);
  }
  return 0;
}