Cod sursă (job #546127)

#include <bits/stdc++.h>
using namespace std;

char a[1005][1005],b[1005][1005];
int nr[1005],m,n,p,q;
int xx,xy,xz,xm,val;


ofstream out("fotografie.out");


void check(int x, int y) {
  for (int i=x;i>x-p;--i) for (int j=y;j>y-q;--j) if(a[i][j]!=b[i-(x-p+1)][j-(y-q+1)]) return;
  out<<x-p+1<<' '<<y-q<<'\n';
}


int main(){
  ifstream cin("fotografie.in");

  cin>>n>>m;
  for(int i=0;i<n;i++) cin>>a[i];
  cin>>p>>q;
  for (int i=0;i<p;i++) cin>>b[i];

  for(int j=0;j<q;++j) for(int i=0;i<p;++i) xm=(xm*26+(b[i][j]-'a'))%46103;
  xx=1;
  xy=1;
  xz=1;
  for (int i=1;i<p;++i) xx=(xx*26)%46103;
  xz=(xx*26)%46103;

  for(int i=1;i<q;++i) xy=(xy*xz)%46103;

  for(int j=0;j<m;++j) for(int i=0;i<p-1;++i) nr[j]=(nr[j]*26+(a[i][j]-'a'))%46103;

  for(int i=p-1;i<n;++i){
    for(int j=0;j<m;++j) nr[j]=(nr[j]*26+(a[i][j]-'a'))%46103;

    val=0;
    for(int j=0;j<q-1;++j) val=(val*xz+nr[j])%46103;

    for(int j=q-1;j<m;++j){
      val=(val*xz+nr[j])%46103;
      if (val==xm) check(i,j);

      val=((val-xy*nr[j-q+1])%46103);
      if (val<0) val+=46103;
    }
    for(int j=0;j<m;++j){
      nr[j]=(nr[j]-xx*(a[i-p+1][j]-'a'))%46103;
      if(nr[j]<46103) nr[j]+=46103;
    }
  }
  return 0;
}