Problem:


Pattern Search

Find places where a R &times C pattern is found within a  H &times; W region. Print top-left coordinates (i, j) of sub-regions where the pattern found. The top-left and bottom-right coordinates of the region is (0, 0) and (H-1, W-1) respectively.

Input

  In the first line, two integers H and W are given. In the following H lines, i-th lines of the region are given.

  In the next line, two integers R and C are given. In the following R lines, i-th lines of the pattern are given.

output

  For each sub-region found, print a coordinate i and j separated by a space character in a line. Print the coordinates in ascending order of the row numbers (i), or the column numbers (j) in case of a tie.

Constraints

  
 1 ≤ H, W ≤ 1000 

  
 1 ≤ R, C ≤ 1000 

  
The input consists of alphabetical characters and digits

Sample Input 1

4 5
00010
00101
00010
00100
3 2
10
01
10

Sample Output 1

0 3
1 2



Sample input:
4 5
00010
00101
00010
00100
3 2
10
01
10


Sample output:
0 3
1 2

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8

def make_KMP_table(pattern): # ????´¢????????????????§???°???????±????????????????????????????
    l = len(pattern)
    table = [0]*l 
    count = 0
    j = 0
    for i in range(1,l):     
        if pattern[i] == pattern[j]:
            table[i] = count
            count += 1
            j += 1
        else:
            table[i] = count
            count = 0
            j = 0       
    return table

def bfs(pattern,buff,x,y):
    count = 0
    for j in range(1,R):
        for i in range(C):
            if pattern[j][i] != buff[y+j][i + x]:
                count = 1
                break
        if count == 1:
            break
    else:
        print(y,x) 
    
    
    
def KMP_search(pattern,buff):
    bl = W
    pl = C
    table = make_KMP_table(pattern[0])
    for y in range(H-R + 1):
        buffplace = 0
        j = 0
        while buffplace < bl:

            if pattern[0][j] != buff[y][buffplace]:
                if j == 0:
                    buffplace += 1
                    
                else:
                     j = table[j]
            elif pattern[0][j] == buff[y][buffplace]:
                buffplace += 1
                j += 1
            if j == pl:
                x = buffplace - j
                bfs(pattern,buff,x,y)
                buffplace -= j - 1
                j = 0        
            

H,W = map(int,input().split())
buff = [0]*H
for i in range(H):
    buff[i] = input()
R,C = map(int,input().split())

pattern = [0] * R
for i in range(R):
    pattern[i] = input()
    
KMP_search(pattern, buff)

Submission status: Time Limit Exceeded

Solution code:
import re

h, w = map(int, input().split())
f = ""

for i in range(h):
    f += input()

r, c = map(int, input().split())

p = input()

for i in range(r - 1):
    line = input()
    p += "."*(w - c) + line

for i in range(len(f) - len(p) + 1):
    tmp = f[i:i + len(p)]
    if re.match(p, tmp) and (i%w <= w - c or i//w == h - r):
        print(i//w, i%w)

Submission status: Time Limit Exceeded

Solution code:
import re

h, w = map(int, input().split())
f = ""

for i in range(h):
    f += input()

r, c = map(int, input().split())

p = input()
p_first = p

for i in range(r - 1):
    line = input()
    p += "."*(w - c) + line

for i in range(len(f) - len(p) + 1):
    if f[i:i + c] == p_first and re.match(p, f[i:i + len(p)]) and (i%w <= w - c or i//w == h - r):
        print(i//w, i%w)

Submission status: Time Limit Exceeded

Solution code:
import re

h, w = map(int, input().split())
f = ""

for i in range(h):
    f += input()

r, c = map(int, input().split())

p = input()
p_first = p

for i in range(r - 1):
    line = input()
    p += "."*(w - c) + line

for i in range(len(f) - len(p) + 1):
    if f[i:i + c] == p_first and (i%w <= w - c or i//w == h - r):
        if re.match(p, f[i:i + len(p)]):
            print(i//w, i%w)

Submission status: Time Limit Exceeded

Solution code:
import re

h, w = map(int, input().split())
f = ""

for i in range(h):
    f += input()

r, c = map(int, input().split())

p = input()
p_first = p

for i in range(r - 1):
    line = input()
    p += "."*(w - c) + line

prog = re.compile(p)
for i in range(len(f) - len(p) + 1):
    if f[i:i + c] == p_first and (i%w <= w - c or i//w == h - r) and prog.match(f[i:i + len(p)]):
        print(i//w, i%w)

Submission status: Time Limit Exceeded

Solution code:
import re

h, w = map(int, input().split())
f = ""

for i in range(h):
    inp = input()
    f = f + inp

r, c = map(int, input().split())

p = input()

for i in range(r - 1):
    line = input()
    p += "."*(w - c) + line

prog = re.compile(p)

i = 0

while True:
    m   = prog.search(f)
    if m == None:
        break
    else:
        idx = m.start()
        i += idx
        f = f[idx + 1:]
        if i%w <= w - c or i//w == h - r:
            print(i//w, i%w)
        i += 1

Submission status: Time Limit Exceeded

Solution code:
import re

h, w = map(int, input().split())
t = ""

for i in range(h):
    inp = input()
    t = t + inp

r, c = map(int, input().split())

p = input()
p0 = p

for i in range(r - 1):
    line = input()
    p += "."*(w - c) + line

prog = re.compile(p)

i = 0
while True:
    f = t.find(p0)
    if f == -1:
        break
    else:
        t = t[f:]
        m = prog.match(t)
        i += f
        if m and (i%w <= w - c or i//w == h - r):
            print(i//w, i%w)
        t = t[1:]
        i += 1

Submission status: Time Limit Exceeded

Solution code:
import re

h, w = map(int, input().split())
f = ""

for i in range(h):
    inp = input()
    f = f + inp

r, c = map(int, input().split())

p = input()

for i in range(r - 1):
    line = input()
    p += "."*(w - c) + line

prog = re.compile(p)

i = 0
while True:
    m   = prog.search(f)
    if m == None:
        break
    else:
        idx = m.start()
        i += idx
        f = f[idx + 1:]
        if i%w <= w - c or i//w == h - r:
            print(i//w, i%w)
        i += 1

Submission status: Time Limit Exceeded

Solution code:
def MAIN():
    H, W = map(int, input().split())
    MAP = [input() for _ in range(H)]
    R, C = map(int, input().split())
    PTN = [input() for _ in range(R)]
    def solve(a, b):
        k = 0
        for i in range(a, a + R):
            if MAP[i][b:b + C] == PTN[k]:
                k += 1
            else:
                return False
        return True
    for i in range(H - R + 1):
        for j in range(W - C + 1):
            if solve(i, j):
                print(i, j)
MAIN()

Submission status: Time Limit Exceeded

Solution code:
def MAIN():
    H, W = map(int, input().split())
    MAP = tuple(input() for _ in range(H))
    R, C = map(int, input().split())
    PTN = tuple(input() for _ in range(R))
    def solve(a, b):
        k = 0
        for i in range(a, a + R):
            if MAP[i][b:b + C] == PTN[k]:
                k += 1
            else:
                return False
        return True
    for i in range(H - R + 1):
        for j in range(W - C + 1):
            if solve(i, j):
                print(i, j)
MAIN()

Submission status: Time Limit Exceeded

Solution code:
def MAIN():
    H, W = map(int, input().split())
    MAP = tuple(input() for _ in range(H))
    R, C = map(int, input().split())
    PTN = tuple(input() for _ in range(R))
    def solve(a, b):
        k = 0
        for i in range(a, a + R):
            if MAP[i][b:b + C] == PTN[k]:
                k += 1
            else:
                return False
        return True
    ans = []
    for i in range(H - R + 1):
        for j in range(W - C + 1):
            if solve(i, j):
                ans.append(f"{i} {j}")
    if ans:
        print(*ans, sep="\n")
MAIN()

Submission status: Time Limit Exceeded

Solution code:
def MAIN():
    H, W = map(int, input().split())
    MAP = tuple(input() for _ in range(H))
    R, C = map(int, input().split())
    PTN = tuple(input() for _ in range(R))
    def solve(a, b):
        k = 0
        for i in range(a, a + R):
            if MAP[i][b:b + C] == PTN[k]:
                k += 1
            else:
                return False
        return True
    ans = []
    for i in range(H - R + 1):
        for j in range(W - C + 1):
            if solve(i, j):
                ans.append(f"{i} {j}")
    if ans:
        print("\n".join(a for a in ans))
MAIN()

Submission status: Time Limit Exceeded

Solution code:
def MAIN():
    H, W = map(int, input().split())
    MAP = tuple(input() for _ in range(H))
    R, C = map(int, input().split())
    PTN = tuple(input() for _ in range(R))
    def solve(a, b):
        k = 0
        for i in range(a, a + R):
            if MAP[i][b:b + C] == PTN[k]:
                k += 1
            else:
                return False
        return True
    ans = []
    for i in range(H - R + 1):
        if PTN[0] not in MAP[i]:
            continue
        for j in range(W - C + 1):
            if solve(i, j):
                ans.append(f"{i} {j}")
    if ans:
        print("\n".join(a for a in ans))
MAIN()

Submission status: Time Limit Exceeded

Solution code:
def MAIN():
    H, W = map(int, input().split())
    MAP = tuple(input() for _ in range(H))
    R, C = map(int, input().split())
    PTN = tuple(input() for _ in range(R))
    def solve(a, b):
        k = 0
        for i in range(a, a + R):
            if MAP[i][b:b + C] == PTN[k]:
                k += 1
            else:
                return False
        return True
    ans = []
    for i in range(H - R + 1):
        j = MAP[i].find(PTN[0])
        while j != -1:
            if solve(i, j):
                ans.append(f"{i} {j}")
            j = MAP[i].find(PTN[0], j + 1)
    if ans:
        print("\n".join(a for a in ans))
MAIN()

Submission status: Time Limit Exceeded

Solution code:
def MAIN():
    H, W = map(int, input().split())
    MAP = tuple(input() for _ in range(H))
    R, C = map(int, input().split())
    PTN = tuple(input() for _ in range(R))
    def solve(a, b):
        k = 0
        for i in range(a, a + R):
            if MAP[i][b:b + C] == PTN[k]:
                k += 1
            else:
                return False
        return True
    ans = []
    for i in range(H - R + 1):
        if PTN[0] not in MAP[i]:
            continue
        j = MAP[i].find(PTN[0])
        while j != -1:
            if solve(i, j):
                ans.append(f"{i} {j}")
            j = MAP[i].find(PTN[0], j + 1)
    if ans:
        print("\n".join(a for a in ans))
MAIN()

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
F=[input()for _ in[0]*H]
R,C=map(int,input().split())
P=[input()for _ in[0]*R]
for h in range(H-R+1):
 for w in range(W-C+1):
  for i in range(R):
   if F[h+i][w:w+C]!=P[i]:break
  else:print(h,w)

Submission status: Accepted

Solution code:
base1 = 1009
base2 = 1013
mask = (1 << 32) - 1


def calculate_hash(f, r, c):
    global ph, pw, h
    tmp = [[0 for _ in range(c)] for _ in range(r)]
    dr, dc = r - ph, c - pw

    t1 = 1
    for _ in range(pw):
        t1 = (t1 * base1) & mask
    for i in range(r):
        e = 0
        for j in range(pw):
            e = e * base1 + f[i][j]
        for j in range(dc):
            tmp[i][j] = e
            e = (e * base1 - t1 * f[i][j] + f[i][j + pw]) & mask
        tmp[i][dc] = e

    t2 = 1
    for _ in range(ph):
        t2 = (t2 * base2) & mask
    for j in range(dc + 1):
        e = 0
        for i in range(ph):
            e = e * base2 + tmp[i][j]
        for i in range(dr):
            h[i][j] = e
            e = (e * base2 - t2 * tmp[i][j] + tmp[i + ph][j]) & mask
        h[dr][j] = e


th, tw = map(int, input().split())
t = [[ord(x) for x in input().strip()] for _ in range(th)]
ph, pw = map(int, input().split())
p = [[ord(x) for x in input().strip()] for _ in range(ph)]

if th >= ph and tw >= pw:
    h = [[0 for _ in range(tw)] for _ in range(th)]
    calculate_hash(p, ph, pw)
    key = h[0][0] & mask
    calculate_hash(t, th, tw)
    for i in range(th - ph + 1):
        for j in range(tw - pw + 1):
            if h[i][j] & mask == key:
                print(i, j)

Submission status: Accepted

Solution code:
base1 = 1009
base2 = 1013
mask = (1 << 32) - 1


def calc_hash(f, r, c):
    global ph, pw, h
    tmp = [[0] * c for _ in range(r)]
    dr, dc = r - ph, c - pw

    t1 = 1
    for _ in range(pw):
        t1 = (t1 * base1) & mask
    for i in range(r):
        e = 0
        for j in range(pw):
            e = e * base1 + f[i][j]
        for j in range(dc):
            tmp[i][j] = e
            e = (e * base1 - t1 * f[i][j] + f[i][j + pw]) & mask
        tmp[i][dc] = e

    t2 = 1
    for _ in range(ph):
        t2 = (t2 * base2) & mask
    for j in range(dc + 1):
        e = 0
        for i in range(ph):
            e = e * base2 + tmp[i][j]
        for i in range(dr):
            h[i][j] = e
            e = (e * base2 - t2 * tmp[i][j] + tmp[i + ph][j]) & mask
        h[dr][j] = e


th, tw = map(int, input().split())
t = [[ord(c) for c in input().strip()] for _ in range(th)]
ph, pw = map(int, input().split())
p = [[ord(c) for c in input().strip()] for _ in range(ph)]

if th >= ph and tw >= pw:
    h = [[0] * tw for _ in range(th)]
    calc_hash(p, ph, pw)
    key = h[0][0] & mask
    calc_hash(t, th, tw)
    for i in range(th - ph + 1):
        for j in range(tw - pw + 1):
            if h[i][j] & mask == key:
                print(i, j)

Submission status: Accepted

Solution code:
base1 = 127
base2 = 1009
mask = (1 << 32) - 1


def calc_hash(f, r, c):
    global ph, pw, h
    tmp = [[0] * c for _ in range(r)]
    dr, dc = r - ph, c - pw

    t1 = 1
    for _ in range(pw):
        t1 = (t1 * base1) & mask
    for i in range(r):
        e = 0
        for j in range(pw):
            e = e * base1 + f[i][j]
        for j in range(dc):
            tmp[i][j] = e
            e = (e * base1 - t1 * f[i][j] + f[i][j + pw]) & mask
        tmp[i][dc] = e

    t2 = 1
    for _ in range(ph):
        t2 = (t2 * base2) & mask
    for j in range(dc + 1):
        e = 0
        for i in range(ph):
            e = e * base2 + tmp[i][j]
        for i in range(dr):
            h[i][j] = e
            e = (e * base2 - t2 * tmp[i][j] + tmp[i + ph][j]) & mask
        h[dr][j] = e


th, tw = map(int, input().split())
t = [[ord(c) for c in input().strip()] for _ in range(th)]
ph, pw = map(int, input().split())
p = [[ord(c) for c in input().strip()] for _ in range(ph)]

if th >= ph and tw >= pw:
    h = [[0] * tw for _ in range(th)]
    calc_hash(p, ph, pw)
    key = h[0][0] & mask
    calc_hash(t, th, tw)
    for i in range(th - ph + 1):
        for j in range(tw - pw + 1):
            if h[i][j] & mask == key:
                print(i, j)

Submission status: Accepted

Solution code:
base1 = 1009
base2 = 1013
mask = (1 << 32) - 1
def calc_hash(f, r, c):
    global ph, pw, h
    tmp = [[0] * c for _ in range(r)]
    dr, dc = r - ph, c - pw
    t1 = 1
    for _ in range(pw):
        t1 = (t1 * base1) & mask
    for i in range(r):
        e = 0
        for j in range(pw):
            e = e * base1 + f[i][j]
        for j in range(dc):
            tmp[i][j] = e
            e = (e * base1 - t1 * f[i][j] + f[i][j + pw]) & mask
        tmp[i][dc] = e
    t2 = 1
    for _ in range(ph):
        t2 = (t2 * base2) & mask
    for j in range(dc + 1):
        e = 0
        for i in range(ph):
            e = e * base2 + tmp[i][j]
        for i in range(dr):
            h[i][j] = e
            e = (e * base2 - t2 * tmp[i][j] + tmp[i + ph][j]) & mask
        h[dr][j] = e
th, tw = map(int, input().split())
t = tuple(tuple(ord(c) for c in input()) for _ in range(th))
ph, pw = map(int, input().split())
p = tuple(tuple(ord(c) for c in input()) for _ in range(ph))
if th >= ph and tw >= pw:
    h = [[0] * tw for _ in range(th)]
    calc_hash(p, ph, pw)
    key = h[0][0] & mask
    calc_hash(t, th, tw)
    for i in range(th - ph + 1):
        for j in range(tw - pw + 1):
            if h[i][j] & mask == key:
                print(i, j)

Submission status: Accepted

Solution code:
base1 = 1009
base2 = 1013
mask = (1 << 32) - 1
def calc_hash(f, r, c):
    global ph, pw, h
    tmp = [[0] * c for _ in range(r)]
    dr, dc = r - ph, c - pw
    t1 = 1
    for _ in range(pw):
        t1 = (t1 * base1) & mask
    for i in range(r):
        e = 0
        for j in range(pw):
            e = e * base1 + f[i][j]
        for j in range(dc):
            tmp[i][j] = e
            e = (e * base1 - t1 * f[i][j] + f[i][j + pw]) & mask
        tmp[i][dc] = e
    t2 = 1
    for _ in range(ph):
        t2 = (t2 * base2) & mask
    for j in range(dc + 1):
        e = 0
        for i in range(ph):
            e = e * base2 + tmp[i][j]
        for i in range(dr):
            h[i][j] = e
            e = (e * base2 - t2 * tmp[i][j] + tmp[i + ph][j]) & mask
        h[dr][j] = e
th, tw = map(int, input().split())
t = tuple(tuple(ord(c) for c in input()) for _ in range(th))
ph, pw = map(int, input().split())
p = tuple(tuple(ord(c) for c in input()) for _ in range(ph))
ans = []
if th >= ph and tw >= pw:
    h = [[0] * tw for _ in range(th)]
    calc_hash(p, ph, pw)
    key = h[0][0] & mask
    calc_hash(t, th, tw)
    for i in range(th - ph + 1):
        for j in range(tw - pw + 1):
            if h[i][j] & mask == key:
                ans.append(f"{i} {j}")
if ans:
    print("\n".join(a for a in ans))

Submission status: Accepted

Solution code:
base1 = 1009
base2 = 1013
mask = (1 << 32) - 1
def calc_hash(f, r, c):
    global ph, pw, h
    tmp = [[0] * c for _ in range(r)]
    dr, dc = r - ph, c - pw
    # t1 = 1
    t1 = (base1 ** pw) & mask
    # for _ in range(pw):
        # t1 = (t1 * base1) & mask
    for i in range(r):
        e = 0
        for j in range(pw):
            e = e * base1 + f[i][j]
        for j in range(dc):
            tmp[i][j] = e
            e = (e * base1 - t1 * f[i][j] + f[i][j + pw]) & mask
        tmp[i][dc] = e
    t2 = 1
    for _ in range(ph):
        t2 = (t2 * base2) & mask
    for j in range(dc + 1):
        e = 0
        for i in range(ph):
            e = e * base2 + tmp[i][j]
        for i in range(dr):
            h[i][j] = e
            e = (e * base2 - t2 * tmp[i][j] + tmp[i + ph][j]) & mask
        h[dr][j] = e
th, tw = map(int, input().split())
t = tuple(tuple(ord(c) for c in input()) for _ in range(th))
ph, pw = map(int, input().split())
p = tuple(tuple(ord(c) for c in input()) for _ in range(ph))
ans = []
if th >= ph and tw >= pw:
    h = [[0] * tw for _ in range(th)]
    calc_hash(p, ph, pw)
    key = h[0][0] & mask
    calc_hash(t, th, tw)
    for i in range(th - ph + 1):
        for j in range(tw - pw + 1):
            if h[i][j] & mask == key:
                ans.append(f"{i} {j}")
if ans:
    print("\n".join(a for a in ans))

Submission status: Accepted

Solution code:
from functools import lru_cache


class MatrixRKSearch:
    shift = 40
    size = 33554393

    def __init__(self, m1, m2):
        self.haystack = self._encode(m1)
        self.needle = self._encode(m2)

    def find(self):
        i1, j1 = len(self.haystack), len(self.haystack[0])
        i2, j2 = len(self.needle), len(self.needle[0])
        if i1 < i2 or j1 < j2:
            return

        hs1 = [self._hash(s, j2) for s in self.haystack]
        hs2 = [self._hash(s, j2) for s in self.needle]
        dm = self.shift**(j2-1) % self.size

        for j in range(j1-j2+1):
            for i in range(i1-i2+1):
                if hs1[i:i+i2] == hs2:
                    yield (i, j)
            if j+j2 < j1:
                for i in range(i1):
                    hs1[i] = self._shift(hs1[i], self.haystack[i][j+j2],
                                         self.haystack[i][j], dm)

    def _shift(self, h, add, remove, dm):
        return ((h - remove*dm) * self.shift + add) % self.size

    def _hash(self, s, length):
        h = 0
        for i in range(length):
            h = (h * self.shift + s[i]) % self.size

        return h

    def _encode(cls, m):
        basea = ord('a')
        based = ord('0')
        es = []
        for s in m:
            bs = []
            for c in s:
                if c.isdigit():
                    bs.append(ord(c) - based + 27)
                else:
                    bs.append(ord(c) - basea)
            es.append(bs)

        return es


def search(matrix, pattern):
    """Search matrix for pattern
    """
    def _check(y, x):
        for m in range(py):
            for n in range(px):
                if matrix[y+m][x+n] != pattern[m][n]:
                    return False
        return True

    mx = len(matrix[0])
    my = len(matrix)
    px = len(pattern[0])
    py = len(pattern)
    for i in range(my-py+1):
        for j in range(mx-px+1):
            if _check(i, j):
                yield (i, j)


def run():
    h, w = [int(x) for x in input().split()]
    m = []

    for _ in range(h):
        m.append(input())

    r, c = [int(x) for x in input().split()]
    pt = []

    for _ in range(r):
        pt.append(input())

    sch = MatrixRKSearch(m, pt)
    result = []
    for i, j in sch.find():
        result.append((i, j))

    result.sort()
    for i, j in result:
        print(i, j)


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
from functools import lru_cache


class MatrixRKSearch:
    shift = 40
    size = 33554393

    def __init__(self, m1, m2):
        self.haystack = self._encode(m1)
        self.needle = self._encode(m2)

    def find(self):
        i1, j1 = len(self.haystack), len(self.haystack[0])
        i2, j2 = len(self.needle), len(self.needle[0])
        if i1 < i2 or j1 < j2:
            return

        hs1 = [self._hash(s, j2) for s in self.haystack]
        hs2 = [self._hash(s, j2) for s in self.needle]
        dm = self.shift**(j2-1) % self.size

        for j in range(j1-j2+1):
            for i in range(i1-i2+1):
                if hs1[i:i+i2] == hs2:
                    yield (i, j)
            if j+j2 < j1:
                for i in range(i1):
                    hs1[i] = self._shift(hs1[i], self.haystack[i][j+j2],
                                         self.haystack[i][j], dm)

    @lru_cache(maxsize=1000)
    def _shift(self, h, add, remove, dm):
        return ((h - remove*dm) * self.shift + add) % self.size

    def _hash(self, s, length):
        h = 0
        for i in range(length):
            h = (h * self.shift + s[i]) % self.size

        return h

    def _encode(cls, m):
        basea = ord('a')
        based = ord('0')
        es = []
        for s in m:
            bs = []
            for c in s:
                if c.isdigit():
                    bs.append(ord(c) - based + 27)
                else:
                    bs.append(ord(c) - basea)
            es.append(bs)

        return es

def run():
    h, w = [int(x) for x in input().split()]
    m = []

    for _ in range(h):
        m.append(input())

    r, c = [int(x) for x in input().split()]
    pt = []

    for _ in range(r):
        pt.append(input())

    sch = MatrixRKSearch(m, pt)
    result = []
    for i, j in sch.find():
        result.append((i, j))

    result.sort()
    for i, j in result:
        print(i, j)


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

mod = 10**9 + 9; p = 13; q = 19

p_table = q_table = None
def prepare(L):
    global p_table, q_table
    p_table = [1]*(L+1); q_table = [1]*(L+1)
    for i in range(L):
        p_table[i+1] = p_table[i] * p % mod
        q_table[i+1] = q_table[i] * q % mod

def rolling_hash(S, W, H):
    D = [[0]*(W+1) for i in range(H+1)]
    for i in range(H):
        su = 0
        dp = D[i]
        di = D[i+1]
        si = S[i]
        for j in range(W):
            v = si[j] # v = ord(si[j]) if si[j] is str
            su = (su*p + v) % mod
            di[j+1] = (su + dp[j+1]*q) % mod
    return D
def get(S, x0, y0, x1, y1):
    P = p_table[x1 - x0]; Q = q_table[y1 - y0]
    return (S[y1][x1] - S[y1][x0] * P - S[y0][x1] * Q + S[y0][x0] * (P * Q) % mod) % mod

def solve():
    prepare(1001)
    H, W = map(int, readline().split())
    M = [list(map(ord, readline().strip())) for i in range(H)]
    R, C = map(int, readline().split())
    M0 = [list(map(ord, readline().strip())) for i in range(R)]

    rh = rolling_hash(M, W, H)
    rh0 = rolling_hash(M0, C, R)
    v = rh0[-1][-1]
    for i in range(H-R+1):
        for j in range(W-C+1):
            if v == get(rh, j, i, j+C, i+R):
                write("%d %d\n" % (i, j))
solve()

Submission status: Accepted

Solution code:
from typing import List


def calc_hash(tab: List[List[int]], row_num: int, col_num: int) -> None:
    global hash_table, R, C, baes1, base2, mask
    tmp_table = [[0] * col_num for _ in range(row_num)]
    diff_row, diff_col = row_num - R, col_num - C

    bit_mask = 1
    for _ in range(C):
        bit_mask = (bit_mask * base1) & mask
    for r in range(row_num):
        hash_v = 0
        for c in range(C):
            hash_v = hash_v * base1 + tab[r][c]
        for dc in range(diff_col):
            tmp_table[r][dc] = hash_v
            hash_v = (hash_v * base1 - bit_mask * tab[r][dc] + tab[r][dc + C]) & mask
        tmp_table[r][diff_col] = hash_v

    bit_mask = 1
    for _ in range(R):
        bit_mask = (bit_mask * base2) & mask
    for c in range(diff_col + 1):
        hash_v = 0
        for r in range(R):
            hash_v = hash_v * base2 + tmp_table[r][c]
        for dr in range(diff_row):
            hash_table[dr][c] = hash_v
            hash_v = (hash_v * base2 - bit_mask * tmp_table[dr][c]
                      + tmp_table[dr + R][c]) & mask
        hash_table[diff_row][c] = hash_v


if __name__ == "__main__":
    base1 = 1009  # The first prime number over 1000.
    base2 = 1013  # The second prime number over 1000.
    mask = (1 << 32) - 1  # Mask.

    H, W = map(lambda x: int(x), input().split())
    region = [[0] * W for _ in range(H)]
    for row in range(H):
        region[row] = [ord(s) for s in input()]

    R, C = map(lambda x: int(x), input().split())
    pattern = [[0] * C for _ in range(R)]
    for row in range(R):
        pattern[row] = [ord(s) for s in input()]

    if H >= R and W >= C:
        hash_table = [[0] * W for _ in range(H)]
        calc_hash(pattern, R, C)  # Calc the target hash and save it into hash_table[0][0]
        key = hash_table[0][0] & mask
        calc_hash(region, H, W)
        for r in range(H - R + 1):
            for c in range(W - C + 1):
                if key == hash_table[r][c] & mask:
                    print(f"{r} {c}")

Submission status: Accepted

Solution code:
from collections import deque
import re
import sys
sys.setrecursionlimit(100000)

class AC:
    
    def __init__(self,num,parent,char):
        self.num = num
        self.parent = parent
        self.char = char
        self.d = {}
        self.failure = None
        
    def insert(self,string,num):
        if not string[0] in self.d:
            self.d[string[0]] = AC(num,self,string[0])
            num+=1
        if not string[1:] == "":
            return self.d[string[0]].insert(string[1:],num)
        else:
            return num
        
    def setFailure(self):
        tmp = self.parent.failure
        while(True):
            if self.char in tmp.d:
                self.failure = tmp.d[self.char]
                break
            else:
                if tmp.num == 0:
                    self.failure = tmp
                    break
                else:
                    tmp = tmp.failure
    
    def setFailureRoot(self):
        self.failure = self
    
    def setFailureFirstLayer(self):
        self.failure = self.parent
       
    def transition(self,string):
        if string == "":
            return []
        elif string[0] in self.d:
            tmp = self.d[string[0]]
            num = "{0:09d}".format(tmp.num) 
            return [num]+tmp.transition(string[1:])
        else:
            if self.num == 0:
                num = "{0:09d}".format(self.num)
                return [num]+self.transition(string[1:])
            else:
                return self.failure.transition(string)
    
H,W = [int(i) for i in input().split()]
A = [input() for _ in range(H)]
R,C = [int(i) for i in input().split()]
B = [input() for _ in range(R)]

root = AC(0,None,"")
root.setFailureRoot()
num=1
for i in B:
    num = root.insert(i,num)
d = deque()
for i in root.d.values():
    i.setFailureFirstLayer()
    for j in i.d.values():
        d.appendleft(j)
while(len(d)>0):
    tmp = d.pop()
    tmp.setFailure()
    for i in tmp.d.values():
        d.appendleft(i)
        
trans = ["" for i in range(W)]
for i in A:
    tmp = root.transition(i)
    for j,k in enumerate(tmp):
        trans[j] = trans[j]+k+"#"

ans=""
for i in B:
    ans = ans+root.transition(i)[-1]+"#"

ansd = deque()
for i,j in enumerate(trans):
    obj = re.search(ans,j)
    c = 0
    while(obj):
        s = obj.start()
        if (i-C+1)<0:
            print(i)
        ansd.append(((c+s)//10,i-C+1))
        obj = re.search(ans,j[c+s+10:])
        c += s+10

for i in sorted(ansd):
    print(i[0],i[1])