Cod sursă (job #579151)

#include<fstream>
#include<iostream>
#define P 73
#define MOD1 100007
#define MOD2 100021
using namespace std;


int i, n, m, ok, N, M;
char mat1[1001][1001], mat2[1001][1001];
int col1[1001][1001], col2[1001][1001];
int main()
{
    freopen("fotografie.in", "r", stdin);
    freopen("fotografie.out", "w", stdout);


    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            scanf(" %c ",&mat1[i][j] );
            mat1[i][j] -= 'a' - 1;

        }
    }
    scanf("%d%d",&N,&M );
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= M; j++)
        {
            scanf(" %c ",&mat2[i][j] );
            mat2[i][j] -= 'a' - 1;
        }
    }
    int pow1 = 1, pow2 = 1, Pow1 = 1, Pow2 = 1;
    for(int i = 1; i <= N - 1; i++)
    {
        pow1 = (pow1 * P) % MOD1;
        pow2 = (pow2 * P) % MOD2;
    }
    for(int i = 1; i <= N * (M - 1); i++)
    {
        Pow1 = (Pow1 * P) % MOD1;
        Pow2 = (Pow2 * P) % MOD2;
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(i >= N)
            {
                col1[i][j] = (1ll * (((col1[i - 1][j] - 1ll * mat1[i - N][j] * pow1)) % MOD1 + MOD1) * P + mat1[i][j]) % MOD1;

                col2[i][j] = (col2[i - 1][j] - 1ll * mat1[i - N][j] * pow2) % MOD2 + MOD2;
                col2[i][j] = (col2[i][j] * P + mat1[i][j]) % MOD2;
            }
            else
            {
                col1[i][j] = (col1[i - 1][j] * P + mat1[i][j]) % MOD1;
                col2[i][j] = (col2[i - 1][j] * P + mat1[i][j]) % MOD2;
            }

        }
    }
    int has1 = 0, has2 = 0;
    for(int j = 1; j <= M; j++)
    {
        for(int i = 1; i <= N; i++)
        {
            has1 = (has1 * P + mat2[i][j]) % MOD1;
            has2 = (has2 * P + mat2[i][j]) % MOD2;
        }
    }
    int H1 = 0, H2 = 0;
    pow1 = pow1 * P % MOD1;
    pow2 = pow2 * P % MOD2;
    for(int i = 3; i <= n; i++)
    {
        H1 = 0, H2 = 0;
        for(int j = 1; j <= m; j++)
        {
            if(j >= M)
            {
                H1 = (1ll * ((H1 - 1ll * col1[i][j - M] * Pow1) % MOD1 + MOD1) * pow1 + col1[i][j]) % MOD1;

                H2 = (1ll * ((H2 - 1ll * col2[i][j - M] * Pow2) % MOD2 + MOD2) * pow2 + col2[i][j]) % MOD2;

                if(H1 == has1 && H2 == has2)
                {
                    cout << i - N  << " " << j - M << endl;
                }
            }
            else
            {
                H1 = (1ll * H1 * pow1 + col1[i][j]) % MOD1;
                H2 = (1ll * H2 * pow2 + col2[i][j]) % MOD2;
            }
        }
    }
}