Problem:
Pattern Search Find places where a R × C pattern is found within a H × 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

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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 = (base1 ** pw) & 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))

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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] 
            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()

Solution (Python):
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  
    base2 = 1013  
    mask = (1 << 32) - 1  

    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)  
        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}")

Solution (Python):
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])