Cod sursă (job #467086)

#include <fstream>

using namespace std ;

ifstream fin("fotografie.in") ;
ofstream fout("fotografie.out") ;

FILE *in = fopen("fotografie.in", "r"), *out = fopen("fotografie.out", "w") ;

const int MAX = 1002 ;
const int mod =  46103 ;

char mat[MAX][MAX], srch[MAX][MAX] ;
int nr[MAX], mx, my, mz, p, q, m, n, sm, val ;

void ok(int x, int y) {
  int i, j ;
  for (i = x ; i > x - p ; -- i) {
    for (j = y ; j > y - q ; -- j) {
      if (mat[i][j] != srch[i - (x - p + 1)][j - (y - q + 1)]) {
        return  ;
      }
    }
  }
  fprintf(out, "%d %d\n", x - p + 1, y - q + 1) ;
}

int main() {
  int i, j ;
  fscanf(in, "%d %d\n", &n, &m) ;
  for (i = 0 ; i < n ; ++ i) {
    fread(mat[i], m + 1, 1, in) ;
  }
  fscanf(in ,"%d %d\n", &p, &q) ;
  for (i = 0 ; i < p ; ++ i) {
    fread(srch[i], q + 1, 1, in) ;
  }

  for (j = 0 ; j < q ; ++ j)
    for (i = 0 ; i < p ; ++ i)
      sm = (sm * 26 + (srch[i][j] - 'a')) % mod ;

  mx = 1 ;
  my = 1 ;
  mz = 1 ;
  for (i = 1 ; i < p ; ++ i)
    mx = (mx * 26) % mod ;

  mz = (mx * 26) % mod ;
  for (i = 1 ; i < q ; ++ i)
    my = (my * mz) % mod ;

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

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

    val = 0 ;
    for (j = 0 ; j < q - 1 ; ++ j)
      val = (val * mz + nr[j]) % mod ;

    for (j = q - 1 ; j < m ; ++ j) {
      val = (val * mz + nr[j]) % mod ;
      if (val == sm)ok(i, j) ;

      val = ((val - my * nr[j - q + 1]) % mod) ;
      if (val < 0)val += mod ;
    }

    for (j = 0 ; j < m ; ++ j) {
      nr[j] = (nr[j] - mx * (mat[i - p + 1][j] - 'a')) % mod ;
      if (nr[j] < mod)
        nr[j] += mod ;
    }
  }
}