Cod sursă (job #400934)

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

ofstream fout("fotografie.out");
ifstream fin("fotografie.in");
u base1[1001], base2[1001], hash[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++)
			hash[j]=hash[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+hash[j];
		if(hashtext==hashpattern)
			fout<<i-1<<' '<<0<<'\n';
		for(int j=q+1; j<=m; j++) {
			hashtext=(hashtext*29989+hash[j]-base2[q]*hash[j-q]);
			if(hashtext==hashpattern)
				fout<<i-1<<' '<<j-q<<'\n';
		}
		for(int j=1; j<=m; j++)
			hash[j]=(hash[j]*137+t[i+p][j]-base1[p]*t[i][j]);
	}
	return 0;
}