Cod sursă (job #124742)

#include<stdio.h>
#define MAX 1000
#define NR 26
#define MOD 46103
char v[MAX][MAX],search[MAX][MAX];
int SRollHash[MAX];
FILE *fout;
void check(int i1,int j1,int p,int q){
    int i,j,i2=i1+p-1,j2=j1+q-1;
    for(i=i1;i<=i2;i++)
        for(j=j1;j<=j2;j++)
            if(search[i-i1][j-j1]!=v[i][j])
                return;
    fprintf(fout,"%d %d\n",i1,j1);
}
int powLog(int nr,int put){
    int rez=1;
    while(put){
        if(put%2==1){
            rez=(rez*nr)%MOD;
        }
        nr=(nr*nr)%MOD;
        put/=2;
    }
    return rez;
}
int main(){
    FILE *fin;
    fin=fopen("fotografie.in","r");
    fout=fopen("fotografie.out","w");
    int n,m;
    fscanf(fin,"%d%d ",&n,&m);
    int i,j;
    for(i=0;i<n;i++){
        for(j=0;j<m;j++)
            v[i][j]=fgetc(fin);
        fgetc(fin);
    }
    int p,q;
    fscanf(fin,"%d%d ",&p,&q);
    int PQ=1,P1=1;
    for(i=1;i<p;i++)
        P1=(P1*NR)%MOD;
    int P=(P1*NR)%MOD;
    for(i=1;i<q;i++)
        PQ=PQ*P%MOD;
    for(i=0;i<p;i++){
        for(j=0;j<q;j++){
            search[i][j]=fgetc(fin);
        }
        fgetc(fin);
    }
    long long hash=0;
    for(j=0;j<q;j++)
        for(i=0;i<p;i++)
            hash=(hash*NR+search[i][j]-'a')%MOD;

    for(j=0;j<m;j++)
        for(i=0;i<p-1;i++)
            SRollHash[j]=(SRollHash[j]*NR+v[i][j]-'a')%MOD;

    for(i=p-1;i<n;i++){

        for(j=0;j<m;j++)
            SRollHash[j]=(SRollHash[j]*NR+v[i][j]-'a')%MOD;

        int tHash=0;
        for(j=0;j<q-1;j++)
            tHash=(tHash*P+SRollHash[j])%MOD;

        for(j=q-1;j<m;j++){
            tHash=(tHash*P+SRollHash[j])%MOD;
            if(tHash==hash)
                check(i-p+1,j-q+1,p,q);
            tHash=(tHash-SRollHash[j-q+1]*PQ)%MOD;
            if(tHash<0)
                tHash+=MOD;
        }

        for(j=0;j<m;j++){
            SRollHash[j]=(SRollHash[j]-(v[i-p+1][j]-'a')*P1)%MOD;
            if(SRollHash[j]<0)
                SRollHash[j]+=MOD;
        }
    }
    return 0;
}