Cod sursă (job #546316)

#include <bits/stdc++.h>
using namespace std;
const int N = 1002;
const int MOD = 10000001;
char a[N][N], b[N][N];
int n, m, p, q, v[N], val1, val2, p1, p2;
long long smen;

int putere(long long x, long long y){

	if(y==1)
	return x;
	if(y%2==0)
	return putere(x*x%MOD, y/2);
	return x* putere(x*x%MOD, (y-1)/2) %MOD;
}
 

int main ()
{
	FILE *in = fopen("fotografie.in","r");
	FILE *out = fopen("fotografie.out","w");
	int i,j,x,y,i1,j1,i2,j2;
	bool buna;
	fscanf(in,"%d%d\n",&n,&m);
	for(int i = 0 ; i < n ; i++)
	fgets(a[i],N,in);
	fscanf(in,"%d%d\n",&p,&q);

	for(int i = 0 ; i < p ; i++)
	fgets(b[i],N,in);

	if(q>1) p1=putere(26,q-1);
	else p1=1;
	if(p>1) p2=putere(26,p-1);
	else p2=1;
	
	for(i = 0 ; i < p ; i++)
	{
		for(j = 0 ; j < q ; j++)
		{
			v[j]=v[j]*26%MOD+b[i][j]-'a';
			if(v[j]>MOD)
			v[j]-=MOD;
		}
	}

	for(j = 0 ; j < q ; j++)
	{
		val1=val1*26%MOD+v[j];
		if(val1>MOD)
		val1-=MOD;
		v[j]=0;
	}

	for(i = 0 ; i < p ; i++)
	{
		for(j = 0 ; j < m ; j++)
		v[j]=(v[j]*26%MOD+a[i][j]-'a')%MOD;
	}

	for(int j = 0 ; j < q ; j++)
	{
		val2=val2*26%MOD+v[j];
		if(val2>MOD)
		val2-=MOD;
	}

	for(i = p - 1 ; i < n ; i++)
	{
		for(j = q - 1 ; j < m ; j++)
		{
			if(val1==val2)
			{
				x=i-p+1; y=j-q+1;
				buna = 1;
				for(i1 = x, i2 = 0 ; i2 < p && buna; i2++,i1++)
				for(j1 = y, j2 = 0 ; j2 < q && buna; j2++,j1++)
				if(a[i1][j1]!=b[i2][j2])
				buna=0;
				if(buna)
				fprintf(out,"%d %d\n",x,y);
			}
			x=j;
			smen=(long long)p1*v[x-q+1];
			smen%=MOD;
			val2=(MOD+val2-smen)*26%MOD+v[x+1];
			if(val2>MOD)
			val2-=MOD;
		}
		x=i;

		for(j1 = 0 ; j1 < m; j1++)
		{
		smen=(long long)p2*(a[x-p+1][j1]-'a');
		smen%=MOD;
		v[j1]=(MOD+v[j1]-smen)*26%MOD+a[x+1][j1]-'a';
		if(v[j1]>MOD)
		v[j1]-=MOD;
		}

		val2=0;

		for(int j1 = 0 ; j1 < q; j1++)
		{
			val2=val2*26%MOD+v[j1];
			if(val2>MOD)
			val2-=MOD;
		}
	}
	return 0;
}