Cod sursă (job #474300)

#pragma GCC optimize("O3")
#include <fstream>
#include <string>

using namespace std;

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

int n, m, p, q;

char first[1005][1005], second;

const unsigned int MOD = 1000000007;
const unsigned int base = 29;

int hash1[1005][1005], hash2[1005];

int main()
{
    in >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            in >> first[i][j];
    in >> p >> q;
    long long put = 1;
    for(int i = 1; i <= q; i++)
        put = (put*base) % MOD;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= q; j++)
            hash1[i][j] = ((long long) hash1[i][j-1] * base + (first[i][j] - 'a')) % MOD;
        for(int j = q+1; j <= m; j++)
        {
            hash1[i][j] = (((long long) hash1[i][j-1] * base + (first[i][j] - 'a')) % MOD - put * (first[i][j-q] - 'a')) % MOD;
            if(hash1[i][j] < 0)
                hash1[i][j] += MOD;
        }
    }
    for(int i = 1; i <= p; i++)
        for(int j = 1; j <= q; j++)
        {
            in >> second;
            hash2[i] = ((long long) hash2[i] * base + (second - 'a')) % MOD;
        }
    for(int i = 1; i <= n - p + 1; i++)
    {
        for(int j = q; j <= m; j++)
        {
            int posi = i;
            while(posi - i + 1 <= p && hash1[posi][j] == hash2[posi-i+1])
                posi++;
            if(posi - i + 1 > p)
                out << i - 1 << ' ' << j - q << '\n';
        }
    }
    return 0;
}