Cod sursă (job #446759)

#include <cstdio>
#include <cstring>
#include <vector>
#define NMAX 1001

#define MOD 1000003
#define PRIM1 3
#define PRIM2 17

using namespace std;

typedef unsigned int ui;

ui n, m, p, q;
char A[NMAX][NMAX], B[NMAX][NMAX];
vector <ui> colHash;
ui hashA, hashB, auxHash, lineP = 1, colP = 1;

int main()
{
    ui i, j;
    freopen("fotografie.in",  "r", stdin);
    freopen("fotografie.out", "w", stdout);

    //read
    scanf("%d%d ", &n, &m);
    colHash = vector <ui> (m, 0);
    for(i=0; i<n; ++i)
        scanf("%s ", A[i]);

    scanf("%d%d ", &p, &q);
    for(i=0; i<p; ++i)
        scanf("%s ", B[i]);

    //PRIME ^ (SZ - 1)
    for(i=1; i<q; ++i) lineP = ((lineP << 4) + lineP) % MOD;
    for(i=1; i<p; ++i) colP = ((colP << 1) + colP) % MOD;

    //hashB
    for(j=0; j<q; ++j){
        //hash for col[i] from B
        auxHash = 0;

        for(i=0; i<p; ++i)
            auxHash = (((auxHash << 1) + auxHash) % MOD + (B[i][j] - '`')) % MOD;

        //hash the columns` hash ;)
        hashB = (((hashB << 4) + hashB) % MOD + auxHash) % MOD;
    }

    //pre-hashing first m columns with p lines
    for(j=0; j<m; ++j)
        for(i=0; i<p; ++i)
            colHash[j] = (((colHash[j] << 1) + colHash[j]) % MOD + (A[i][j] - '`')) % MOD;

    //for each line calculate the new submatrix hash by moving left -> right
    for(i=0; i + p<=n; ++i){
        hashA = 0;

        //first submatrix hash using pre-hashes
        for(j=0; j<q; ++j)
            hashA = (((hashA << 4) + hashA) % MOD + colHash[j]) % MOD;

        if(hashA == hashB)
            printf("0 0\n");

        //move to the right
        for(j=q; j<m; ++j){
            auxHash = hashA - ((colHash[j - q] * lineP) % MOD) + MOD;
            hashA   = (((auxHash << 4) + auxHash) % MOD) + colHash[j];

            if(hashA == hashB)
                printf("%d %d\n", i, j - q + 1);
        }

        //prepare for moving down
        for(j=0; j<m; ++j){
            auxHash    = colHash[j] - (((A[i][j] - '`') * colP) % MOD) + MOD;
            colHash[j] = (((auxHash << 1) + auxHash) % MOD) + (A[i + p][j] - '`');
        }
    }

    return 0;
}