Cod sursă (job #416520)

#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 k=0;
    mat[i][1]=0;
    for(int q=2; q<=y; ++q)
    {
        while(k>0 && s[i][k+1]!=s[i][q]) k=mat[i][k];
        if(s[i][k+1]==s[i][q]) ++k;
        mat[i][q]=k;
    }
}

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);
    int t=y;
    for(int d=1; d<=n-x+1; ++d){
        ok=1;
        q=0;
        int I=x;
        int i=1;
        for(int j=1; j<=m; ++j){
            while(q>0 && s[i][q+1]!=a[d][j])
                q=mat[i][q];
            if(s[i][q+1]==a[d][j])
                ++q;
            if(q==y){
                q=mat[i][y];

                for(I=x; I>=2 && ok; --I){
                    for(t=y; t>=1 && ok; --t){
                        if(s[I][t]!=a[d-x+I+3][j+t-y]){
                            ok=0;
                        }
                    }
                }
                if(ok)g<<d-1<<' '<<j-y<<'\n';
                ok=1;
            }
        }
        //cout<<ok<<' ';
    }
    /*
    for(int i=1; i<=x; ++i){
        for(int j=1; j<=y; ++j)
            g<<mat[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;
}