Cod sursă (job #92333)

#include<cstdio>
using namespace std;

FILE *in = fopen("fotografie.in","r");
FILE *out = fopen("fotografie.out","w");

const int Lm = 1002;
const int MOD = 1000001;
char mat[Lm][Lm], pat[Lm][Lm];
int n, m, p, q, v[Lm], hash1, hash2, pow1, pow2;
long long aux;

int power(long long a, long long b){
    if(b==1)
        return a;
    if(b%2==0)
        return power(a*a%MOD, b/2)%MOD;
    return a* power(a*a%MOD, (b-1)/2) %MOD;
}

void hash_pattern(){
    for(int i = 0 ; i < p ; i++){
        for(int j = 0 ; j < q ; j++){
            v[j]=(v[j]*26%MOD+pat[i][j])%MOD;
        }
    }
    for(int j = 0 ; j < q ; j++){
        hash1=(hash1*26%MOD+v[j])%MOD;
        v[j]=0;
    }
}

void hash_mat(){
     for(int i = 0 ; i < p ; i++){
        for(int j = 0 ; j < m ; j++){
            v[j]=(v[j]*26%MOD+mat[i][j])%MOD;
        }
    }
    for(int j = 0 ; j < q ; j++)
        hash2=(hash2*26%MOD+v[j])%MOD;
}

void move_right(int x){
    aux=(long long)pow1*v[x-q+1];
    aux%=MOD;
    hash2=((MOD+hash2-aux)*26%MOD+v[x+1])%MOD;
}

void move_down(int x){
    for(int j = 0 ; j < m; j++){
        aux=(long long)pow2*mat[x-p+1][j];
        aux%=MOD;
        v[j]=((MOD+v[j]-aux)*26%MOD+mat[x+1][j])%MOD;
    }
    hash2=0;
    for(int j = 0 ; j < q; j++)
        hash2=(hash2*26%MOD+v[j])%MOD;
}

void verif(int x, int y){
    bool ok = 1;
    for(int i = x, i2 = 0 ; i2 < p && ok; i2++,i++)
        for(int j = y, j2 = 0 ; j2 < q && ok; j2++,j++)
            if(mat[i][j]!=pat[i2][j2])
                ok=0;
    if(ok){
        fprintf(out,"%d %d\n",x,y);
    }
}

int main (){
    fscanf(in,"%d%d\n",&n,&m);
    for(int i = 0 ; i < n ; i++){
        fgets(mat[i],Lm,in);
    }
    fscanf(in,"%d%d\n",&p,&q);
    for(int i = 0 ; i < p ; i++){
        fgets(pat[i],Lm,in);
    }
    if(q>1) pow1=power(26,q-1);
    else pow1=1;
    if(p>1) pow2=power(26,p-1);
    else pow2=1;

    hash_pattern();
    hash_mat();
    for(int i = p - 1 ; i < n ; i++){
        for(int j = q - 1 ; j < m ; j++){
            if(hash1==hash2)
                verif(i-p+1,j-q+1);
            move_right(j);
        }
        move_down(i);
    }

    return 0;
}