HackerRank The Grid Search Solution

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
static void print_grid(char **grid, int R, int C) {
  for (int i = 1; i <= R; ++i) {
    fprintf(stderr, "%s\n", grid[i]);
  }
}
static char **get_grid(int R, int C) {
  char **grid = malloc((R+1)*sizeof(*grid));
  for (int i = 1; i <= R; ++i) {
    grid[i] = malloc((C+2)*sizeof(*grid[i]));
    scanf("%s", grid[i]);
  }
  return grid;
}
static void free_grid(char **grid, int R, int C) {
  for (int i = 1; i <= R; ++i) {
    free(grid[i]);
  }
  free(grid);
}
int main() {
  int num_tests = 0;
  scanf("%d", &num_tests);
  for (int i = 0; i < num_tests; ++i) {
    int R, C;
    scanf("%d %d", &R, &C);
    char **grid = get_grid(R, C);
    //print_grid(grid, R, C);
    int r, c;
    scanf("%d %d", &r, &c);
    char **pattern = get_grid(r, c);
    //print_grid(pattern, r, c);
    int found = 0;
    for (int i = 1; i <= R-r+1; ++i) {
      for (int j = 0; j <= C-c; ++j) {
        found = 1;
        int abort = 0;
        for (int a = 0; a < r; ++a) {
          if (abort) break;
          for (int b = 0; b < c; ++b) {
            if (grid[i+a][j+b] != pattern[a+1][b]) {
              abort = 1;
              found = 0;
              break;
            }
          }
        }
        if (found) break;
      }
      if (found) break;
    }
    printf("%s\n", found ? "YES" : "NO");
    free_grid(grid, R, C);
    free_grid(pattern, r, c);
  }
  return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
typedef unsigned int LL;
struct MatHash {
    typedef unsigned int LL;
    #define MAXN 1001
    #define MAXM 1001
    #define TIME 2
    static LL P[TIME], Q[TIME], MOD[TIME];
    static LL powerP[TIME][MAXN], powerQ[TIME][MAXM];
    int n, m;
    int mat[MAXN][MAXM];
    LL h[TIME][MAXN][MAXM];//???hash?
    static void init(int id) {
        powerP[id][0] = 1;
        for (int i = 1; i < MAXN; i++) {
            powerP[id][i] = (powerP[id][i - 1] * P[id]);
        }
        powerQ[id][0] = 1;
        for (int i = 1; i < MAXM; i++) {
            powerQ[id][i] = (powerQ[id][i - 1] * Q[id]);
        }
    }
    void inithash(int id) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                h[id][i][j] = (mat[i][j] + 3) * powerP[id][n - 1 - i] * powerQ[id][m - 1 - j];
                if (i) h[id][i][j] = (h[id][i][j] + h[id][i - 1][j]);
                if (j) h[id][i][j] = (h[id][i][j] + h[id][i][j - 1]);
                if (i && j) h[id][i][j] = (h[id][i][j] - h[id][i - 1][j - 1]);
            }
        }
    }
    LL gethash(int x1, int y1, int x2, int y2, int id) {
        LL ret = h[id][x2][y2];
        if (x1) ret = (ret - h[id][x1 - 1][y2]);
        if (y1) ret = (ret - h[id][x2][y1 - 1]);
        if (x1 && y1) ret = (ret + h[id][x1 - 1][y1 - 1]);
        ret = (ret * powerP[id][x1]);
        ret = (ret * powerQ[id][y1]);
        return ret;
    }
    LL resize(int x1, int y1, int x2, int y2, int id, int _n, int _m) {
        LL ret = gethash(x1, y1, x2, y2, id);
        ret = ret * powerP[id][_n - n] * powerQ[id][_m - m];
        return ret;
    }
    void input() {
        for (int i = 0; i < n; i++) {
            getchar();
            for (int j = 0; j < m; j++) {
                mat[i][j] = getchar() - '0';
            }
        }
    }
}A, B;
LL MatHash::P[TIME], MatHash::Q[TIME], MatHash::MOD[TIME];
LL MatHash::powerP[TIME][MAXN], MatHash::powerQ[TIME][MAXM];
int main() {
    MatHash::P[0] = 393241, MatHash::Q[0] = 784633, MatHash::MOD[0] = 805306457;
    MatHash::P[1] = 784633, MatHash::Q[1] = 111117, MatHash::MOD[1] = 402653189;
    for (int i = 0; i < TIME; i++) {
        MatHash::init(i);
    }
    int cases;
    scanf("%d", &cases);
    for (int T = 0; T < cases; T++) {
        scanf("%d %d", &A.n, &A.m);
        A.input();
        for (int i = 0; i < TIME; i++) {
            A.inithash(i);
        }
        scanf("%d %d", &B.n, &B.m);
        B.input();
        for (int i = 0; i < TIME; i++) {
            B.inithash(i);
        }
        bool yes = false;
        for (int id = 0; id < TIME; id++) {
            B.inithash(id);
            LL val = B.resize(0, 0, B.n - 1, B.m - 1, id, A.n, A.m);
            for (int i = B.n - 1; i < A.n; i++) {
                for (int j = B.m - 1; j < A.m; j++) {
                    if (A.gethash(i - B.n + 1, j - B.m + 1, i, j, id) == val) {
                        yes = true;
                        break;
                    }
                }
                if (yes) break;
            }
        }
        puts(yes ? "YES" : "NO");
    }
}

import java.util.*;
public class Solution {
  public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);
    
    int T = cin.nextInt();
    for (int set = 0; set < T; set++) {
      int R = cin.nextInt();
      int C = cin.nextInt();
      cin.nextLine(); //Skip end-of-line character to get to the grid
      
      String[] grid = new String[R];
      for (int i = 0; i < R; i++)
        grid[i] = cin.nextLine();
      
      int r = cin.nextInt();
      int c = cin.nextInt();
      cin.nextLine();
      String[] subgrid = new String[r];
      for (int i = 0; i < r; i++)
        subgrid[i] = cin.nextLine();
      
      boolean found = false;
      for (int i = 0; !found && i < R-r + 1; i++) { //iterates over "top rows" for the subgrid.
        for (int j = 0; !found && j < C-c + 1; j++) { //iterates over "left-cols" for the subgrid.
         // System.err.println("Now checking "+ grid[i].substring(j, j+c));
          if (subgrid[0].equals(grid[i].substring(j, j+c))) { //We've found a first row!  so, let's check all the rows below
            System.err.println("We found a substring at row=" + i + ", col=" + j);
            found = true;
            for (int k = i+1; found && k < r + i; k++) {
              System.err.println("  The substring = " + grid[k].substring(j, j+c));
              found &= subgrid[k-i].equals(grid[k].substring(j, j+c));
            }
          }
        }
      }
      
      System.out.println(found ? "YES" : "NO");
      
    }
  }
}

def find_all(string, substring):
    index = []
    L = len(string)
    l = len(substring)
    for i in xrange(L-l+1):
        if string[i:i+l] == substring:
            index.append(i)
    return index
def find_pattern(grid, pattern):
    R, C = len(grid), len(grid[0])
    r, c = len(pattern), len(pattern[0])
    for i in xrange(R-r+1):
        indeces = find_all(grid[i], pattern[0])        
        if indeces:
            for idx in indeces:
                for j in xrange(i+1, i+r):
                    if pattern[j-i] != grid[j][idx:idx+c]:
                        break
                else:
                    print 'YES'
                    return
    print 'NO'
    return
 
def main():
    T = input()
    for i in xrange(T):
        R, C = map(int, raw_input().strip().split())
        N = R * C
        grid = []
        for k in xrange(R):
            grid.append(raw_input().strip())
        r, c = map(int, raw_input().strip().split())
        pattern = []
        for k in xrange(r):
            pattern.append(raw_input().strip())
        find_pattern(grid, pattern)
if __name__ == '__main__':
    main()

function cint (str) {
    return parseInt(str);
}
function processData(input) {
    var cases = [], lines = input.trim().split('\n'), lineNo = 1, dims, haystack, needle;
    for (var i = 0; i < parseInt(lines[0]); i++) {
        dims = lines[lineNo++].split(' ').map(cint);
        haystack = [];
        needle = [];
        for (var j = 0; j < dims[0]; j++) {
            haystack.push(lines[lineNo++].split('').map(cint));
        }
        dims = lines[lineNo++].split(' ').map(cint);
        for (var j = 0; j < dims[0]; j++) {
            needle.push(lines[lineNo++].split('').map(cint));
        }
        cases.push({haystack: haystack, needle: needle});
    }
    
    process.stdout.write(cases.map(processCase).join('\n'));
}
function processCase(c) {
    var jumpAmt = {
        0: [1, 1],
        1: [1, 1],
        2: [1, 1],
        3: [1, 1],
        4: [1, 1],
        5: [1, 1],
        6: [1, 1],
        7: [1, 1],
        8: [1, 1],
        9: [1, 1]},
        H = c.haystack.length,
        W = c.haystack[0].length,
        h = c.needle.length,
        w = c.needle[0].length,
        searchElem = c.needle[h - 1][w - 1],
        minVertJump, jump,
        i, j, k, l, m, n;
    for (i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {
            jump = jumpAmt[c.needle[i][j]];
            jumpAmt[c.needle[i][j]] = [Math.min(jump[0], h - i), Math.min(jump[1], w - j)];
        }
    }
    
    for (i = H - 1; i >= h - 1; i -= minVertJump) {
        minVertJump = 1;
        cell: for (j = W - 1; j >= w - 1; j -= jump[1]) {
            if (c.haystack[i][j] === searchElem) {
                for (k = 0, m = i - h + 1; m <= i; k++, m++) {
                    for (l = 0, n = j - w + 1; n <= j; l++, n++) {
                        // console.dir({i: i, j: j, k: k, l: l, m: m, n: n});
                        if (c.haystack[m][n] !== c.needle[k][l]) {
                            continue cell;
                        }
                    }
                }
                return 'YES';
            }
            jump = jumpAmt[c.haystack[i][j]];
            minVertJump = Math.min(minVertJump, jump[0]);
        }
    }
    
    return 'NO';
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});
process.stdin.on("end", function () {
   processData(_input);
});

object Solution {
    def main(args: Array[String]) {
        val t = readInt()
        for (_ <- 0 until t) {
            val Array(r, c) = readLine().split(" ").map(_.toInt)
            val big = (0 until r).map(_ => readLine())
            val Array(rr, cc) = readLine().split(" ").map(_.toInt)
            val small = (0 until rr).map(_ => readLine())
            val isOk = (0 to r - rr).exists(i => {
                val j = big(i).indexOf(small(0))
                if (j < 0) {
                    false
                } else {
                    val end = j + cc
                    (1 until rr).forall(k => big(i + k).substring(j, end) == small(k))
                }
            })
            println(if (isOk) "YES" else "NO")
        }
    }
}

var t, rr, cc, r, c: word;
    p, s: array [1..1000, 1..1000] of char;
    i, j, i0, j0: word;
    ok, br: boolean;
begin
  readln(t);
  while (t>0) do begin
    readln(rr, cc);
    for i:= 1 to rr do begin
      for j:= 1 to cc do begin
        read(p[i, j]);
      end;
      readln;
    end;
    readln(r, c);
    for i:= 1 to r do begin
      for j:= 1 to c do begin
        read(s[i, j]);
      end;
      readln;
    end;
    ok:= false;
    for i0:= 1 to rr-r+1 do begin
      for j0:= 1 to cc-c+1 do begin
        br:= false;
        for i:= 1 to r do begin
          for j:= 1 to c do begin
            if s[i, j]<>p[i0+i-1,j0+j-1] then begin
              br:= true;
              break;
            end;  
          end;
          if br then break;
        end;
        if not br then begin
          ok:= true;
          break;
        end;  
      end;
      if ok then break;
    end;
    if ok then writeln('YES')
          else writeln('NO'); 
    dec(t);      
  end;
end.