Cod sursă (job #546892)

#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;
}