Cod sursă (job #465935)

#include <fstream>

using namespace std;

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

long long base1[1001], base2[1001], hashes[1001];
char a[1001][1001], b[1001][1001];
int n, m, p, q;

inline void initialize()
{
    base1[0] = base2[0] = 1;
    for (int i = 1; i <= 1000; ++i)
    {
        base1[i] = base1[i - 1] * 137;
        base2[i] = base2[i - 1] * 29989;
    }
}

inline void rabinKarp()
{
    long long hp = 0, ht;
    for (int j = 1; j <= m; ++j)
    {
        for (int i = 1; i <= p; ++i)
            hashes[j] = hashes[j] * 137 + a[i][j];
    }
    for (int j = 1; j <= q; ++j)
    {
        long long code = 0;
        for (int i = 1; i <= p; ++i)
            code = code * 137 + b[i][j];
        hp = hp * 29989 + code;
    }
    for (int i = 1; i + p - 1 <= n; ++i)
    {
        ht = 0;
        for (int j = 1; j <= q; ++j)
            ht = ht * 29989 + hashes[j];
        if (ht == hp)
            out << i - 1 << " " << 0 << '\n';
        for (int j = q + 1; j <= m; ++j)
        {
            ht = ht * 29989 + hashes[j] - base2[q] * hashes[j - q];
            if (ht == hp)
                out << i - 1 << " " << j - q << '\n';
        }
        for (int j = 1; j <= m; ++j)
            hashes[j] = hashes[j] * 137 + a[i + p][j] - base1[p] * a[i][j];
    }
}

int main()
{
    in >> n >> m;
    for (int i = 1; i <= n; ++i)
        in >> (a[i] + 1);
    in >> p >> q;
    for (int i = 1; i <= p; ++i)
        in >> (b[i] + 1);
    initialize();
    rabinKarp();
    return 0;
}