Cod sursă (job #759098)

#include <bits/stdc++.h>


using namespace std;

#define ll long long
#define NMAX 200
#define MOD 10000009
#define HASH_SIZE 10009
#define HASH_BASE 10007

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

int lgput(int a,int b)
{
    if(!b)
    {
        return 1;
    }
    int p = lgput(a,b/2) % HASH_SIZE;
    if(b%2)
    {
        return p*p*a % HASH_SIZE;
    }
    return p*p % HASH_SIZE;
}
int a[NMAX+1][NMAX+1],b[NMAX+1][NMAX+1];
int h1[NMAX+1],h2[NMAX+1];
int pf[NMAX+1][NMAX+1];

int n,m,p,q;

int 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++)
    {
        int hashValue = 0;
        for(int i=1;i<=p;i++)
        {
            hashValue = (HASH_BASE * hashValue + b[i][j]) % HASH_SIZE;
        }
        hashPat = (hashPat * HASH_BASE + hashValue ) % HASH_SIZE;
        h1[j]=hashValue;
    }

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

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

    }
}