Cod sursă (job #91262)

#include <stdio.h>
#include <stdlib.h>

#define MAX 1000
#define MOD 1000000007
#define p	5003
#define q	7001

long long pp[MAX + 1], pq[MAX + 1]; // Puterile lui p si ale lui q
int h[MAX + 1][MAX + 1]; // Santinela la N si W

void init() // Calcularea puterilor lui p si q modulo MOD
{
	int i;
	pp[0] = pq[0] = 1;
	for (i = 1; i <= MAX; i++) {
		pp[i] = (pp[i - 1] * p) % MOD;
		pq[i] = (pq[i - 1] * q) % MOD;
	}
}

int main()
{
	FILE *fin, *fout;
	fin = fopen("fotografie.in", "r");
	fout = fopen("fotografie.out", "w");
	init();

	// Citire
	int M, N;
	fscanf(fin, "%d%d", &M, &N);

	int i, j;
	for (i = 1; i <= M; i++) { // Creem hash-ul pt matricea 1
		fgetc(fin); // Sarim peste <Enter>
		for (j = 1; j <= N; j++) {
			long long read = fgetc(fin);
			long long here = (((read * pp[i]) % MOD) * pq[j]) % MOD;
			long long compute = here + (long long)(h[i - 1][j]) + (long long)(h[i][j - 1]) - (long long)(h[i - 1][j - 1]);
			h[i][j] = (compute % MOD + MOD) % MOD;
		}
	}
	
	int P, Q;
	fscanf(fin, "%d%d", &P, &Q);
	long long check = 0;
	for (i = 1; i <= P; i++) {
		fgetc(fin); // Sarim peste <Enter>
		for (j = 1; j <= Q; j++) {
			long long read = fgetc(fin);
			check = (check + ((read * pp[i]) % MOD) * pq[j]) % MOD;
		}
	}

	// Mathcing-ul
	for (i = P; i <= M; i++) {
		for (j = Q; j <= N; j++) {
			long long lhs = ((h[i][j] - h[i - P][j] - h[i][j - Q] + h[i - P][j - Q]) % MOD + MOD) % MOD;
			long long rhs = (((check * pp[i - P]) % MOD) * pq[j - Q]) % MOD;
			if (lhs == rhs) {
				fprintf(fout, "%d %d\n", i - P, j - Q);
			}
		}
	}

	fclose(fin);
	fclose(fout);
	return 0;
}