Cod sursă (job #416476)

#include <bits/stdc++.h>
#define MOD 100003

using namespace std;

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


char a[1001][1001];
char s[1001][1001];
short mat[1001][1001];
int n,m,x,y,ok,q,nr;

void make_prefix(int i){
    int q=0;
    for(int j=2; j<=y; ++j){
        while(q && s[i][j+1]!=s[i][j])
            q=mat[i][q];
        if(s[i][q+1]==s[i][j])
            ++q;
        mat[i][j]=q;
    }
}

int main(){
    f>>n>>m;
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=m; ++j)
            f>>a[i][j];
    }
    f>>x>>y;
    for(int i=1; i<=x; ++i)
        for(int j=1; j<=y; ++j)
            f>>s[i][j];
    for(int i=1; i<=x; ++i)
        make_prefix(i);
    for(int d=1; d<=n-x+1; ++d){
        ok=1;
        q=0;
        int i=1;
        for(int j=1; j<=m; ++j){
            while(q && s[i][q+1]!=a[d][j])
                q=mat[i][q];
            if(s[i][q+1]==a[d][j])
                ++q;
            if(q==y){
                for(int I=2; I<=x && ok; ++I)
                    for(int J=1; J<=y&& ok; ++J)
                        if(s[I][J]!=a[d+I-1][j-y+J]){
                            ok=0;
                        }
                if(ok)g<<d-1<<' '<<j-y<<'\n';
                ok=1;
            }
        }
    }
    /*
    for(int i=1; i<=x; ++i){
        for(int j=1; j<=y; ++j)
            g<<s[i][j];
        g<<'\n';
    }
    g<<'\n';
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=m; ++j)
            g<<a[i][j];
        g<<'\n';
    }
    */
    return 0;
}