Cod sursă (job #546494)

#include <bits/stdc++.h>
using namespace std;
#define MOD1 3407
#define MOD2 9973

	ifstream fi ("fotografie.in");
    ofstream fo ("fotografie.out");
    
int pow1[1001],pow2[1001],h[1001];
char A[1001][1001],B[1001][1001];
int n,m,p,q;

int main(){
    
    fi >> n >> m;
    
    for(int i=1; i<=n; i++)
        fi >> A[i]+1;
        
   fi >> p >> q;
   
    for(int i=1; i<=p; i++)
        fi >> B[i]+1;
        
    pow1[0]=pow2[0]=1;
    
    for(int i=1; i<=1000; ++i){
        pow1[i]=pow1[i-1]*MOD1;
        pow2[i]=pow2[i-1]*MOD2;
    }
    
    int h1=0;
    for(int j=1; j<=m; j++)
        for(int i=1; i<=p; i++)
            h[j]=h[j]*MOD1+A[i][j];
            
    for(int j=1; j<=q; j++)
	{
        int code=0;
        for(int i=1;i<=p; i++)
            code=code*MOD1+B[i][j];
        h1=h1*MOD2+code;
    }
    
    for(int i=1; i<=n+1-p; i++)
	{
        int h2=0;
        for(int j=1; j<=q; j++)
            h2=h2*MOD2+h[j];
            
        if(h2==h1)
            fo<<i-1<<" "<<0<<'\n';
            
        for(int j=q+1; j<=m; j++){
            h2=(h2*MOD2+h[j]-pow2[q]*h[j-q]);
            
            if(h2==h1)
                fo<<i-1<<" "<<j-q<<'\n';
        }
        for(int j=1; j<=m; j++)
            h[j]=(h[j]*MOD1+A[i+p][j]-pow1[p]*A[i][j]);
    }
    
    return 0;
}