Cod sursă (job #758938)

#include <iostream>
#include <fstream>
#include <vector>
#define N_MAX 1005

using namespace std;

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

char bigFoto[N_MAX][N_MAX], smallFoto[N_MAX][N_MAX];
int table[N_MAX];
vector <int> potential;
int n, m, p, q;

void makeTable (){
    int k = 0, i = 1;

    while (i<q){
        if (smallFoto[0][i] == smallFoto[0][k]){
            ++k;
            table[i] = k;
            ++i;
        }
        else if (k != 0)
            k = table[k-1];
        else
            ++i;
    }
}

void kmp (int idx){
    potential.clear();

    int k = 0, i = 0;

    while (i<m){
        if (smallFoto[0][k] == bigFoto[idx][i]){
            ++k;
            ++i;
            if (k == q){
                potential.push_back(i-q);
                k = table[k-1];
            }
        }
        else{
            if (k == 0)
                ++i;
            else
                k = table[k-1]; 
        }
    }
}

int main (){
    in >> n >> m;
    for (int i=0; i<n; ++i)
        for (int j=0; j<m; ++j)
            in >> bigFoto[i][j];
    
    in >> p >> q;
    for (int i=0; i<p; ++i)
        for (int j=0; j<q; ++j)
            in >> smallFoto[i][j];

    makeTable();

    bool ok = true;
    for (int i=0; i<=n-p; ++i){
        kmp(i);
        for (int j:potential){
            ok = true;
            for (int k=1; k<p; ++k){
                for (int t=0; t<q; ++t){
                    if (smallFoto[k][t] != bigFoto[i+k][j+t])
                        ok = false;
                }
            }
            if (ok == true){
                out << i << ' ' << j << '\n';
            }
        }
    }
}