Cod sursă (job #546325)

#include <cstdio>

#include <algorithm>

#define MAX_N 1000
#define MAX_M 1000

#define MAX_P 1000
#define MAX_Q 1000

#define MOD1 40013
#define MOD2 40031
#define MOD3 40009

#define CHARS 26

#define DEBUG 0

using namespace std;

FILE *f, *g;

int n, m;
int p, q;

char s[MAX_M + 2];

char a[MAX_N + 1][MAX_M + 1];
char b[MAX_N + 1][MAX_M + 1];

int sum[MAX_M + 1];

void readFile()
{
    f = fopen("fotografie.in", "r");

    fscanf(f, "%d%d", &n, &m);

    char c;
    fscanf(f, "%c", &c);///'\n'

    int i, j;
    for(i = 1; i <= n; i ++)
    {
        fgets(s, MAX_M + 2, f);

        for(j = 1; j <= m; j ++)
            a[i][j] = s[j - 1] - 'a' + 1;
    }

    fscanf(f, "%d%d", &p, &q);

    fscanf(f, "%c", &c);///'\n'
    for(i = 1; i <= p; i ++)
    {
        fgets(s, MAX_Q + 2, f);

        for(j = 1; j <= q; j ++)
            b[i][j] = s[j - 1] - 'a' + 1;
    }

    fclose(f);
}

int r1, r2;

int col;

void getHash()
{
    int sumcol = 0;

    int i, j;
    for(i = 1; i <= q; i ++)
    {
        sumcol = 0;
        for(j = 1; j <= p; j ++)
        {
            sumcol = (sumcol * CHARS + b[j][i]) % MOD3;
        }

        r1 = (r1 * col + sumcol) % MOD1;
        r2 = (r2 * col + sumcol) % MOD2;
    }
}

int putere(int a, int b, int MOD)
{
    int rez = 1;
    int ca = a;
    int i;
    for(i = 0; (1 << i) <= b; i ++)
    {
        if(((1 << i) & b) != 0)
        {
            rez *= ca;
            rez %= MOD;
        }

        ca *= ca;
        ca %= MOD;
    }

    return rez;
}
/*
void getSums()
{
    int ant;
    int i, j;
    for(i = 1; i <= m; i ++)
    {
        for(j = 1; j <= n; j ++)
        {
            ant = sum[j - 1][i];

            if(j - 1 >= p)
            {
                ant += MOD3;
                ant -= (col * a[j - p][i]) % MOD3;

                if(ant >= MOD3)
                    ant %= MOD3;
            }

            sum[j][i] = (ant * CHARS + a[j][i]) % MOD3;
        }
    }
}*/

void solve()
{
    col = putere(CHARS, p - 1, MOD3);

    getHash();

  //  getSums();

    int i, j;

    int p1 = putere(col, q - 1, MOD1);
    int p2 = putere(col, q - 1, MOD2);

    int h1 = 0;
    int h2 = 0;

    g = fopen("fotografie.out", "w");

    int ant;

    for(i = 1; i <= p - 1; i ++)
    {
        for(j = 1; j <= m; j ++)
        {
            ant = sum[j];

            sum[j] = (ant * CHARS + a[i][j]) % MOD3;
        }
    }

    for(i = p; i <= n; i ++)
    {
        for(j = 1; j <= m; j ++)
        {
            ant = sum[j];

            if(i - 1 >= p)
            {
                ant += MOD3;
                ant -= (col * a[i - p][j]) % MOD3;

                if(ant >= MOD3)
                    ant %= MOD3;
            }

            sum[j] = (ant * CHARS + a[i][j]) % MOD3;
        }

        h1 = h2 = 0;
        for(j = 1; j <= m; j ++)
        {
            if(j > q)
            {
                h1 += MOD1;
                h1 -= (sum[j - q] * p1) % MOD1;

                if(h1 >= MOD1)
                    h1 %= MOD1;

                h2 += MOD2;
                h2 -= (sum[j - q] * p2) % MOD2;

                if(h2 >= MOD2)
                    h2 %= MOD2;
            }

            h1 = (h1 * col) % MOD1 + sum[j];

            if(h1 >= MOD1)
                h1 %= MOD1;

            h2 = (h2 * col) % MOD2 + sum[j];

            if(h2 >= MOD2)
                h2 %= MOD2;

            if(j >= q)
            {
                if(h1 == r1 && h2 == r2)
                {
                    fprintf(g, "%d %d\n", i - p, j - q );
                }
            }
        }
    }

    fclose(g);
}

int main()
{
    readFile();

    solve();

    return 0;
}