Cod sursă (job #411867)

#include <cstdio>
using namespace std;
int pow1[1001],pow2[1001],h[1001];
char A[1001][1001],B[1001][1001];
#define MOD1 3407
#define MOD2 9973
int n,m,p,q;
int main(){
    freopen("fotografie.in","r",stdin);
    freopen("fotografie.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%s",A[i]+1);
    scanf("%d %d",&p,&q);
    for(int i=1;i<=p;++i)
        scanf("%s",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 hashpattern=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];
        hashpattern=hashpattern*MOD2+code;
    }
    for(int i=1;i<=n+1-p;++i){
        int hashtext=0;
        for(int j=1;j<=q;++j)
            hashtext=hashtext*MOD2+h[j];
        if(hashtext==hashpattern)
            printf("%d %d\n",i-1,0);
        for(int j=q+1; j<=m; ++j){
            hashtext=(hashtext*MOD2+h[j]-pow2[q]*h[j-q]);
            if(hashtext==hashpattern)
                printf("%d %d\n",i-1,j-q);
        }
        for(int j=1; j<=m; ++j)
            h[j]=(h[j]*MOD1+A[i+p][j]-pow1[p]*A[i][j]);
    }
    return 0;
}