Cod sursă (job #641034)

#include <bits/stdc++.h>
#define mod 100003
#define prim1 17
#define prim2 127
using namespace std;
ifstream f("fotografie.in");
ofstream g("fotografie.out");
long long n,m,p,q,lp=1,cp=1,hasha,hashb,auxh,i,j;
char a[1001][1001],b[1001][1001];
vector<long long> colh;
int main()
{
    //prim1 nr prim pentru hash-urile pe coloane
    //prim2 nr prim pentru hash-urile de pe linii
    f>>n>>m;
    for(i=0; i<n; i++) f>>a[i];
    f>>p>>q;
    for(i=0; i<p; i++) f>>b[i];
    colh=vector<long long>(m,0);
    for(i=1;i<p;i++) cp=cp*prim1%mod;
    for(i=1;i<q;i++) lp=lp*prim2%mod;
   for(j=0;j<q;j++)
    {
        auxh=0;
        for(i=0;i<p;i++)
            auxh=auxh*prim1+b[i][j]-'a'+1;
        hashb=hashb*prim2+auxh;
    }
  //hashb hasul ptr matricea a doua
    for(j=0;j<m;j++)
        for(i=0;i<p;i++)
    {
        colh[j]=colh[j]*prim1+a[i][j]-'a'+1; //hash-urile pe coloane a cate p linii
    }
    for(i=0;i+p<=n;++i)
    {
        hasha=0;
        for(j=0;j<q;j++) hasha=hasha*prim2+colh[j];//hahs-urile pe primele q coloane
        if(hasha==hashb) g<<0<<" "<<i<<'\n';
        for(j=q;j<m;++j)
        {
            auxh=hasha-(colh[j-q]*lp);
            hasha=auxh*prim2+colh[j];//mut la dreapta
            if(hasha==hashb) g<<i<<" "<<j-q+1<<'\n';

        }
        for(j=0;j<m;j++)//mut jos
        {
            auxh=colh[j]-(a[i][j]-'a'+1)*cp;
            colh[j]=auxh*prim1+a[i+p][j]-'a'+1;
        }
    }

    return 0;
}