Cod sursă (job #446812)

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

#define MOD 1000003
#define PRIM1 17
#define PRIM2 127

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;

ui power(ui x, ui n)
{
    if (n == 0) return 1;
    if (n == 1) return x;

    ui tmpAns = power(x, n/2);

    if(n & 1) return x * tmpAns * tmpAns;
    return tmpAns * tmpAns;
}

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)
    lineP = power(PRIM2, q - 1);
    colP  = power(PRIM1, p - 1);

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

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

        //hash the columns` hash ;)
        hashB = ((hashB << 7) - hashB) + auxHash;
    }

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

    //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 << 7) - hashA) + colHash[j];

        if(hashA == hashB)
            printf("%d 0\n", i);

        //move to the right
        for(j=q; j<m; ++j){
            auxHash = hashA - (colHash[j - q] * lineP);
            hashA   = ((auxHash << 7) - auxHash) + 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);
            colHash[j] = ((auxHash << 4) + auxHash) + (A[i + p][j] - '`');
        }
    }

    return 0;
}