Cod sursă (job #546314)

#include <stdio.h>

#define DMAX 1000
#define MOD 46103
#define SIGMA 26

typedef char photo[1 + DMAX][2 + DMAX];

photo a,b;
int csum[DMAX];

int main(){
    int m,n,p,q;
    int hasha, hashb;
    int sigmaP1;
    int sigmaP;
    int sigmaPQ1;
    FILE *f = fopen("fotografie.in","r");
    fscanf(f, "%d%d\n", &m, &n);
    for (int i=0;i<m;++i)
        fgets(a[i], DMAX + 2, f);
    fscanf(f, "%d%d\n", &p, &q);
    for (int i=0;i<p;++i)
        fgets(b[i], DMAX + 2, f);
    fclose(f);
    b[p][0] = 'Z';
    sigmaP1 = 1;
    for (int i=0;i<p-1;i++)
        sigmaP1 = sigmaP1 * SIGMA % MOD;
    sigmaP = sigmaP1 * SIGMA % MOD;
    sigmaPQ1 = 1;
    for (int i=0;i<q-1;++i)
        sigmaPQ1 = sigmaPQ1 * sigmaP % MOD;
    hashb = 0;
    for (int j=0;j<q;++j)
        for (int i=0;i<p;++i)
            hashb = (hashb * SIGMA + (b[i][j] - 'a')) % MOD;
    for (int j=0;j<n;++j)
        for (int i=0;i<p-1;++i)
            csum[j] = (csum[j] * SIGMA + (a[i][j] - 'a')) % MOD;
    f = fopen("fotografie.out","w");
    for (int dl=p-1;dl<m;++dl) {
        for (int j=0;j<n;++j)
            csum[j] = (csum[j] * SIGMA + (a[dl][j] - 'a')) % MOD;
        hasha = 0;
        for (int j=0;j<q-1;++j)
            hasha = (hasha * sigmaP + csum[j]) % MOD;
        for (int dc=q-1;dc<n;++dc) {
            hasha = (hasha * sigmaP + csum[dc]) % MOD;
            if (hasha == hashb) {
                int i = 0, j = 0;
                while (b[i][j] == a[i + dl - p + 1][j + dc - q + 1])
                    if (++j == q)
                        ++i,j=0;
                if (i == p)
                    fprintf(f, "%d %d\n", dl - p + 1, dc - q + 1);
            }
            hasha = (hasha - csum[dc - q + 1] * sigmaPQ1) % MOD;
            if (hasha < 0)
                hasha += MOD;
        }
        for (int j=0;j<n;++j) {
            csum[j] = (csum[j] - (a[dl - p + 1][j] - 'a') * sigmaP1) % MOD;
            if (csum[j] < 0)
                csum[j] += MOD;
        }
    }
    fclose(f);
    return 0;
}