Cod sursă (job #92334)

#include<cstdio>
using namespace std;

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

const int Lm = 1002;
const int MOD = 10000001;
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);
    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]-'a';
            if(v[j]>MOD)
                v[j]-=MOD;
        }
    }
    for(int j = 0 ; j < q ; j++){
        hash1=hash1*26%MOD+v[j];
        if(hash1>MOD)
            hash1-=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]-'a')%MOD;
        }
    }
    for(int j = 0 ; j < q ; j++)
    {
        hash2=hash2*26%MOD+v[j];
        if(hash2>MOD)
            hash2-=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];
    if(hash2>MOD)
        hash2-=MOD;
}

void move_down(int x){
    for(int j = 0 ; j < m; j++){
        aux=(long long)pow2*(mat[x-p+1][j]-'a');
        aux%=MOD;
        v[j]=(MOD+v[j]-aux)*26%MOD+mat[x+1][j]-'a';
        if(v[j]>MOD)
            v[j]-=MOD;
    }
    hash2=0;
    for(int j = 0 ; j < q; j++)
    {
        hash2=hash2*26%MOD+v[j];
        if(hash2>MOD)
            hash2-=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;
}