-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmatrix_hash.py
56 lines (50 loc) · 3.85 KB
/
matrix_hash.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import numpy as np
pa = [1, 19260817, 370979071507489, 7145360007135659758513, 137625471496558636782983085121, 2650779021033932032846505916611003857, 51056169631573715675094539549261805475971169, 983383539994698759628027383957594120362278583385073, 18940770404650073779322423513395956112573821497599131584641, 364814712602981020100027583288016559224315774855922812810690311697, 7026629418353611082619952976662745240189208089713130663671961737268876449, 135338623353725344351514794832106406788905382390884192210074203052537909079798833, 2606732457448030125816510136053747225688664200545842894351064781415774052348643719226561, 50207796830866795263838777309176327478247060141164780098846192509994224935635646874222172960337, 967043186732505294953265407255797664290588106166968996329118425081769437542114973121015290731399215329, 18626041850751612437625868561584391000928452335258561282968821756828171172691606290243794368979276440395463793, 358752783521668119616035768830730185125329750522637796554547692563885905401888426192434608726540320310868435747098881, 6909871711651465186658575208902998072075098389472180956720373624245267232825084431310489783148496152629020052001129827845777, 133089774531595638742101658579417416617591280336618403998276036548214855287540344241020413893592868220991624110924245407379015019809, 2563417791824324315809730241294638828084184631359305478242863055440478004374796950543298085268749707309635230533299591654617657936792523953, 49373520982872406795461420996941881548823940778824044063533266866899901234788163476572514996811783931294446512054695841034317914489158370826849601]
pb = [1, 114, 12996, 1481544, 168896016, 19254145824, 2194972623936, 250226879128704, 28525864220672256, 3251948521156637184, 370722131411856638976, 42262322980951656843264, 4817904819828488880132096, 549241149460447732335058944, 62613491038491041486196719616, 7137937978387978729426426036224, 813724929536229575154612568129536, 92764641967130171567625832766767104, 10575169184252839558709344935411449856, 1205569287004823709692865322636905283584, 137434898718549902904986646780607202328576]
def get_matrix_hash(m, size_x, size_y):
h = [[0 for __ in range(size_y + 1)] for _ in range(size_x + 1)]
for i in range(size_x):
for j in range(size_y):
h[i + 1][j + 1] = h[i][j + 1] * 19260817 + h[i + 1][j] * 114 - h[i][j] * 19260817 * 114 + m[i][j]
return h
def hash(h, a_x, a_y, b_x, b_y):
return h[b_x + 1][b_y + 1] - h[a_x][b_y + 1] * pa[b_x - a_x + 1] - h[b_x + 1][a_y] * pb[b_y - a_y + 1] + h[a_x][a_y] * pa[b_x - a_x + 1] * pb[b_y - a_y + 1]
def matrix_find_cnt(a, b):
h1 = get_matrix_hash(a, len(a), len(a[0]))
h2 = get_matrix_hash(b, len(b), len(b[0]))
ans = 0
for i in range(len(a)):
if i + len(b) - 1 < len(a):
for j in range(len(a[0])):
if j + len(b[0]) - 1 < len(a[0]):
if hash(h1, i , j, i + len(b) - 1, j + len(b[0]) - 1) == h2[len(b)][len(b[0])]:
ans += 1
return ans
if __name__ == "__main__":
a = [
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
]
b = [
[1, 1],
[0, 0]
]
print(matrix_find_cnt(a, b))