fork(4) download
  1. def read_matrix():
  2. nrows, ncols = map(int, raw_input().split())
  3. matrix = [raw_input() for _ in xrange(nrows)]
  4. assert all(len(row) == ncols for row in matrix)
  5. return matrix
  6.  
  7. def count_pattern(pattern, text):
  8. """A naive O(N**2 * M**2) algorithm."""
  9. nrows, ncols = len(pattern), len(pattern[0])
  10. return sum(pattern == [row[j:j+ncols] for row in text[i:i+nrows]]
  11. for i in xrange(len(text) - nrows + 1)
  12. for j in xrange(len(text[i]) - ncols + 1))
  13.  
  14. for _ in xrange(int(raw_input())):
  15. print count_pattern(read_matrix(), read_matrix())
  16.  
Success #stdin #stdout 0.01s 7732KB
stdin
1
2 3
XXX
.X.
5 16
...XXX...X.X.XXX
X...X...XX.X.XX.
....X.X.........
X....X....XXX...
....XXX....X....
stdout
2