Cod sursă (job #758945)

#include <bits/stdc++.h>

#define NMAX 1000
#define HASH_BASE 10009
#define HASH_SIZE 10007
using namespace std;
ifstream fin("fotografie.in");
ofstream fout("fotografie.out");

int lgput(int a,int b)
{
    if(b==0)
    {
        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 n,m;
int p,q;

int a[NMAX+1][NMAX+1];
int b[NMAX+1][NMAX+1];

int v[NMAX+1];
int pf[NMAX+1][NMAX+1];
int hashP=0;

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

    for(int j=1;j<=m;j++)
    {
        for(int i=1;i<=n;i++)
        {
             pf[i][j] = pf[i-1][j] + (1 << a[i][j]);
             if(i > p)
             {
                pf[i][j] -= 1 << (a[i-p][j]);
             }
        }
    }

    for(int i=p;i<=n;i++)
    {
        int hashValue=0;
        for(int j=1;j<=q;j++)
        {
            hashValue = (HASH_BASE * hashValue + pf[i][j])%HASH_SIZE;
        }
        if(hashValue == hashP)
        {
            fout << i-p << " " << q-1 << '\n';
        }
        int pwr = lgput(HASH_BASE,q-1);
        for(int j=q+1;j<=m;j++)
        {
            hashValue = (hashValue - pwr * pf[i][j-q] + HASH_SIZE ) % HASH_SIZE;
            hashValue = (HASH_BASE * hashValue + pf[i][j]) % HASH_SIZE;

            if(hashValue == hashP)
            {
                fout << i-p << " " << j-q << "\n";
            }
        }
    }
    return 0;
}
/// dp[t][n] =