Cod sursă (job #759104)

#include <bits/stdc++.h>


using namespace std;

#define ll long long
#define NMAX 1000
#define MOD 10000009
#define HASH_SIZE 1000009
#define HASH_BASE 1000007

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

ll put(ll a,int b)
{
    ll res=1;
    for(int i=1;i<=b;i++)
    {
        res = res * a % HASH_SIZE;
    }
    return res;
}
int a[NMAX+1][NMAX+1],b[NMAX+1][NMAX+1];
ll h2[NMAX+1];


int n,m,p,q;

ll hashPat;

bool naiv(int x,int y)
{
    bool ok=1;
    for(int i=1;i<=p && ok;i++)
    {
        for(int j=1;j<=q && ok;j++)
        {
            ok = b[i][j] == a[x+i-1][y+j-1];
        }
    }
    return ok;
}
int main()
{
    fin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            char x;
            fin >> x;
            a[i][j]=x-'a'+1;
        }
    }
    fin >> p >> q;
    for(int i=1;i<=p;i++)
    {
        for(int j=1;j<=q;j++)
        {
            char x;
            fin >> x;
            b[i][j]=x-'a'+1;
        }
    }
    for(int j=1;j<=q;j++)
    {
        ll hashValue = 0;
        for(int i=1;i<=p;i++)
        {
            hashValue = (HASH_BASE * hashValue + (ll)b[i][j]) % HASH_SIZE;
        }
        hashPat = (hashPat * HASH_BASE + hashValue ) % HASH_SIZE;
    }

    for(int j=1;j<=m;j++)
    {
        ll hashValue=0;
        for(int i=1;i<=p-1;i++)
        {
            hashValue = (HASH_BASE * hashValue + (ll)a[i][j]) % HASH_SIZE;
        }
        h2[j] = hashValue;
    }
    ll pwr1 = put(HASH_BASE,p-1);
    ll pwr2 = put(HASH_BASE,q-1);

    for(int i=p;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            h2[j] = (h2[j] - (ll)a[i-p][j] *  pwr1 % HASH_SIZE + HASH_SIZE ) % HASH_SIZE;
            h2[j] = (h2[j] * HASH_BASE + (ll)a[i][j]) % HASH_SIZE;
        }
        ll hashValue = 0;
        for(int j=1;j<=q-1;j++)
        {
            hashValue = ( hashValue * HASH_BASE + h2[j] ) % HASH_SIZE;
        }
        for(int j=q;j<=m;j++)
        {
            hashValue = (hashValue - pwr2 * h2[j-q] % HASH_SIZE + HASH_SIZE ) % HASH_SIZE;
            hashValue = (hashValue * HASH_BASE + h2[j] ) % HASH_SIZE;
            if(hashValue == hashPat && naiv(i-p+1,j-q+1))
            {
                fout << i-p << " " << j-q << '\n';
            }
        }

    }
}