Cod sursă (job #310694)

#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_N + 1][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;

void getHash()
{
    int sumlin = 0;

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

        /*if(DEBUG)
        printf("%d\n", sumlin);*/

        r1 = (r1 * MOD3 + sumlin) % MOD1;
        r2 = (r2 * MOD3 + sumlin) % 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 p1 = putere(CHARS, q - 1, MOD3);

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

            if(j - 1 >= q)
            {
                ant += MOD3;
                ant -= p1 * a[i][j - 1 - q + 1];

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

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

            /*if(DEBUG)
            if(j >= q)
            if(sum[i][j] == 2135)
                printf("TERM PE %d %d\n", i, j);*/
        }
    }
}

int rez;

struct rzul
{
    int i, j;
};

rzul rz[MAX_N * MAX_M + 1];

void solve()
{
    getHash();

    getSums();

    int i, j;

    int p1 = putere(MOD3, p - 1, MOD1);
    int p2 = putere(MOD3, p - 1, MOD2);

    int h1 = 0;
    int h2 = 0;

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

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

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

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

            h1 = (h1 * MOD3) % MOD1 + sum[i][j + q - 1];

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

            h2 = (h2 * MOD3) % MOD2 + sum[i][j + q - 1];

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

            if(i >= p)
            {
                if(h1 == r1 && h2 == r2)
                {
                    ++ rez;

                    rz[rez].i = i - p;
                    rz[rez].j = j - 1;
                }
            }
        }
    }
}

bool cmp(rzul a, rzul b)
{
    if(a.i != b.i)
        return a.i < b.i;

    return a.j < b.j;
}

void printFile()
{
    sort(rz + 1, rz + rez + 1, cmp);

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

    int i;
    for(i = 1; i <= rez; i ++)
    {
        fprintf(g, "%d %d\n", rz[i].i, rz[i].j);
    }

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}