Cod sursă (job #400911)

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

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

ofstream fout("fotografie.out");
ifstream fin("fotografie.in");
ull base1[1001], base2[1001];
ull hashes[1001];
char S[1001][1001], T[1001][1001];
int N, M;
int P, Q;

void rabin() {
	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;
	}
	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)
			fout<<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)
				fout<<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() {
	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]*BASE1;
		base2[i]=base2[i-1]*BASE2;
	}
	rabin();
	return 0;
}