Cod sursă (job #641035)

#include <bits/stdc++.h>

using namespace std;
ifstream fin("fotografie.in");
ofstream fout("fotografie.out");
#define prim1 17
#define prim2 127
#define MOD1 1000003
char A[1001][1001],B[1001][1001];
long long n,m,p,q,l1,c1,hash1,colh[1001],hasha,hashb;
int main()
{
    fin>>n>>m;
    for(int i=0;i<n;i++)fin>>A[i];
    fin>>p>>q;
    for(int i=0;i<p;i++)fin>>B[i];
    l1=c1=1;
    for(int i=1;i<=q-1;i++)l1=(l1*prim2)%MOD1;
    for(int i=1;i<=p-1;i++)c1=(c1*prim1)%MOD1;
    //fout<<char(int('a'-1));
    for(int j=0;j<q;j++)
    {
        hash1=0;
        for(int i=0;i<p;i++)
        {
            hash1=(hash1*prim1+(B[i][j]-'a'+1));
        }
        hashb=((hashb*prim2)+hash1);
    }
    for(int j=0;j<m;j++)
    {
        for(int i=0;i<p;i++)
        {
            colh[j]=(colh[j]*prim1+(A[i][j]-'a'+1));
        }
    }
    for(int i=0;i<=n-p;i++)
    {
        hasha=0;
        for(int j=0;j<q;j++)
        {
            hasha=((hasha*prim2)+colh[j]);
        }
        if(hasha==hashb)fout<<i<<" "<<0<<'\n';
        for(int j=q;j<m;j++)
        {
            hash1=hasha-colh[j-q]*l1;
            hasha=hash1*prim2-colh[j];
            if(hasha==hashb)fout<<i<<" "<<j-q+1<<'\n';
        }
        for(int j=0;j<m;j++)
        {
            hash1=colh[j]-(A[i][j]-'a'+1)*c1;
            colh[j]=hash1*prim1+(A[i+p][j]-'a'+1);
        }
    }
    //fout<<"KYS";
    return 0;
}