Cod sursă (job #92335)

#include <stdio.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;
}

void hash_btern(){

}

void hash_a(){

}


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