Cod sursă (job #546232)

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

}