Cod sursă (job #286024)

#include <fstream>

using namespace std;

ifstream in("fotografie.in");
ofstream out("fotografie.out");

const int NMAX = 1000;
const int MOD  = 666013;
const int MOD2 = 696961;

char v[NMAX+4][NMAX+4];
char a[NMAX+4][NMAX+4];
int N, M, P, Q;
int h[NMAX+4][NMAX+4];
int mat[NMAX+4], hhashh = 0;

int main()
{
    in >> N >> M;
    for( int i = 1;  i <= N;  ++i ) {
        string s;
        in >> s;
        for( int j = 1;  j <= M;  ++j ) {
            v[i][j] = s[j-1];
        }
    }
    in >> P >> Q;
    for( int i = 1;  i <= P;  ++i ) {
        string s;
        in >> s;
        for( int j = 1;  j <= Q;  ++j ) {
            a[i][j] = s[j-1];
        }
    }
    for( int i = 1;  i <= N;  ++i ) {
        int key = 0, p = 1;
        for( int ind = 1;  ind <= Q;  ++ind ) {
            p = p*27 % MOD;
            key = ( key * 27 * 1LL + (int)( v[i][ind] - 'a' + 1 ) ) % MOD;
        }
        h[i][1] = key;
        for( int ind = Q+1;  ind <= M;  ++ind ) {
            key = ( key*27*1LL + (int)( v[i][ind] - 'a' + 1 ) - 1LL*p*(v[i][ind-Q]-'a'+1)%MOD + MOD ) % MOD;
            h[i][ind-Q+1] = key;
        }

       /// for( int j = 1;  j <= M-Q+1;  ++j ) out << h[i][j] << ' ';
       /// out << '\n';

        key = 0, p = 1;
        for( int ind = 1;  ind <= Q;  ++ind ) {
            p = p*27 % MOD;
            key = ( key * 27 * 1LL + (int)( a[i][ind] - 'a' + 1 ) ) % MOD;
        }
        mat[i] = key;
    }

    for( int j = 1;  j <= M-Q+1;  ++j ) {
        int key = 0, p = 1;
        for( int ind = 1;  ind <= P;  ++ind ) {
            p = 1LL*p*MOD % MOD2;
            key = ( 1LL*key*MOD + h[ind][j] ) % MOD2;
        }
        h[0][j] = key;
        for( int ind = P+1;  ind <= N;  ++ind ) {
            key = ( 1LL*key*MOD%MOD2 + h[ind][j] - 1LL*p*h[ind-P][j]%MOD2 + MOD2 ) % MOD2;
            h[ind-P][j] = key;
        }

        key = 0, p = 1;
        for( int ind = 1;  ind <= P;  ++ind ) {
            p = 1LL*p*MOD % MOD2;
            key = ( 1LL*key*MOD + mat[ind] ) % MOD2;
        }
        hhashh = key;
    }/*
    out << "hehe\n";
    for( int i = 0;  i < N-P+1;  ++i ) {
        for( int j = 1;  j <= M-Q+1;  ++j ) out << h[i][j] << ' ';
        out << '\n';
    }
    out << "rasp\n";*/
    for( int i = 0;  i < N-P+1;  ++i ) {
        for( int j = 1;  j <= M-Q+1;  ++j ) {
            if( h[i][j] == hhashh ) {
                out << i << ' ' << j-1 << '\n';
            }
        }
    }

    return 0;
}