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: Wrong Answer

Solution code:
def rabin_karp(T, P, d):
    n = len(T)
    m = len(P)
    if n < m:
        return
    h = 1
    p = 0
    t0 = 0
    for _ in range(m - 1):
        h *= d
    for i in range(m):
        p = d * p + P[i]
        t0 = d * t0 + T[i]
    # print("h = ", h)
    # print("p = ", p)
    for s in range(n - m + 1):
        # print("t0 = ", t0)
        if p == t0:
            print(s)
        if s < n - m:
            # print("     ", t0 - T[s] * h)
            # print("     ",  d)
            # print("     ", T[s + m])
            t0 = d * (t0 - T[s] * h) + T[s + m]


d = 1009
t = list(map(ord, input()))
p = list(map(ord, input()))

rabin_karp(t, p, d)

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
def get_common(string,len_string):
    common_length=[0]*len_string
    tmp=0
    tmp_tmp=0
    for i in range(1,len_string):
        if(string[i]==string[tmp]):
            tmp_tmp=tmp
            while(string[i]==string[tmp_tmp] and tmp_tmp >0):
                tmp_tmp=common_length[max([tmp_tmp-1,0])]
            common_length[i-1]=tmp_tmp
            tmp+=1
        else:
            common_length[i-1]=tmp
            while(string[i]!=string[tmp] and tmp>0):
                tmp=common_length[max([tmp-1,0])]
            if(string[i]==string[tmp]):
                tmp+=1

    if(string[-1]==string[tmp-1]):
        common_length[-1]=tmp
    common_length[0]=0
    return common_length



def find_str(field,field_row,pattern,common_length,H,W,h,w):
    tmp=0
    column_list=[]
    len_pattern=len(pattern[0])
    for i in range(len(field[field_row])):
        if(field[field_row][i]!=pattern[0][tmp]):
            while(field[field_row][i]!=pattern[0][tmp] and tmp>0):
                tmp=common_length[0][max([tmp-1,0])]
            if(field[field_row][i]==pattern[0][tmp]):
                tmp+=1
        else:
            tmp+=1
            if(tmp==len_pattern):
                column_list.append(i-tmp+1)
                tmp=common_length[0][-1]
    
    
    
    for j in range(1,h):
        tmp=0
        loop=0
        while( loop  <len(column_list)):
            column=column_list[loop]
            if(loop < len(column_list) -1):
                next_column=column_list[loop+1]
            else:
                next_column=len(field[0])+len(pattern[0])+1
            ini_tmp=tmp
            for i in range(0,len_pattern+1):
                if(field[field_row+j][column+ i+ini_tmp]!=pattern[j][tmp]):
                    if(i < next_column - column):
                        tmp=0
                        column_list.pop(loop)
                        break
                    else:
                        while(tmp>column+i-next_column+1):
                            tmp=common_length[0][max([tmp-1,0])]
                        if(tmp!=column+i-next_column+1):
                            tmp=0
                        column_list.pop(loop)
                        break
                else:
                    tmp+=1
                    if(tmp==len_pattern):
                        if(i < next_column - column):
                            tmp=0
                            loop+=1
                            break
                        else:
                            while(tmp>column+i-next_column+1):
                                tmp=common_length[0][max([tmp-1,0])]
                            if(tmp!=column+i-next_column+1):
                                tmp=0
                            loop+=1
                            break
    for column in column_list:
        print(f"{field_row} {column}")










H,W=map(int,input().split())
field=[]
for i in range(H):
    field.append(input())
h,w=map(int,input().split())
pattern=[]
for i in range(h):
    pattern.append(input())

common_length=[]
for i in range(h):
    common_length.append(get_common(pattern[i],w))

for i in range(H-h+1):
    find_str(field,i,pattern,common_length,H,W,h,w)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
text = [input() for _ in range(h)]
r, c = map(int, input().split())
pat = [input() for _ in range(r)]
cur = 0
for i, line in enumerate(text):
    for j in range(w - c + 1):
        if line[j:j + c] == pat[cur]:
            if cur == r - 1:
                print(i - r + 1, j)
                break
            else:
                cur += 1
                break
    else:
        cur = 0

Submission status: Wrong Answer

Solution code:
def ns_search(t, p):
    global w, c
    for i in range(w - c + 1):
        if t[i:i + c] == p:
            return i
    return -1


def pattern_search(text, pat):
    global h, r
    for i in range(h):
        if h - i < r:
            break
        tmp = ns_search(text[i], pat[0])
        if tmp != -1:
            for j in range(1, r):
                if ns_search(text[i+j], pat[j]) == -1:
                    break
            else:
                print(i, tmp)

h, w = map(int, input().split())
text = [input() for _ in range(h)]
r, c = map(int, input().split())
pat = [input() for _ in range(r)]
pattern_search(text, pat)

Submission status: Wrong Answer

Solution code:
def pattern_search(text, pat):
    def ns_search(t, p, f=-1):
        global w, c
        if f != -1:
            if t[f:f + c] == p:
                return 1
            else:
                return -1
        for i in range(w - c + 1):
            if t[i:i + c] == p:
                return i
        return -1
    global h, r
    for i in range(h):
        if h - i < r:
            break
        tmp = ns_search(text[i], pat[0])
        if tmp != -1:
            for j in range(1, r):
                if ns_search(text[i+j], pat[j], tmp) == -1:
                    break
            else:
                print(i, tmp)

h, w = map(int, input().split())
text = [input() for _ in range(h)]
r, c = map(int, input().split())
pat = [input() for _ in range(r)]
pattern_search(text, pat)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
T = [input() for i in range(H)]
R, C = map(int, input().split())
P = [input() for i in range(R)]

def match(ox, oy):
	for y in range(R):
		for x in range(C):
			if T[oy + y][ox + x] != P[y][x]:
				return False
	return True

for y in range(H - R):
	for x in range(W - C):
		if T[y][x] == P[0][0]:
			print("a")
			if match(x, y):
				print("{0} {1}".format(y, x))

Submission status: Wrong Answer

Solution code:
CSIZE = 256

def make_bm_table(pattern,size):
    bm_table = [size]*CSIZE
    for i in range(size):
        dist = size-i-1
        charac = pattern[i]
        bm_table[ord(charac)] = dist
    return bm_table

def bm_search(pattern,buff): 
        size = len(pattern[0])
        bm_table = make_bm_table(pattern[0], size)    
        buffsize = W
        for j in range(H-C):
            saikobi = size
            while saikobi < buffsize:
                for i in range(size):
                    if pattern[0][size-i-1] != buff[j][saikobi-i]:
                        saikobi += max(bm_table[ord(buff[j][saikobi-i])]-i,1)
                        break
                else:
                    count = 1
                    for k in range(1,R):
                        for l in range(C)[::-1]: 
                            if pattern[k][size-1-l] != buff[j+k][saikobi-l]:
                                count = 0
                                break
                        if count == 0:
                            break
                    else:
                        print(j,saikobi-C+1)
                    saikobi += 1  
                    
            

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


bm_search(pattern, buff)

Submission status: Wrong Answer

Solution code:
CSIZE = 256

def make_bm_table(pattern,size):
    bm_table = [size]*CSIZE
    for i in range(size):
        dist = size-i-1
        charac = pattern[i]
        bm_table[ord(charac)] = dist
    return bm_table

def bm_search(pattern,buff): 
        size = C
        bm_table = make_bm_table(pattern[0], size)    
        buffsize = W
        for j in range(H-C):
            saikobi = size-1
            while saikobi < buffsize:
                for i in range(size):
                    if pattern[0][size-i-1] != buff[j][saikobi-i]:
                        saikobi += max(bm_table[ord(buff[j][saikobi-i])]-i,1)
                        break
                else:
                    count = 1
                    for k in range(1,R):
                        for l in range(C)[::-1]: 
                            if pattern[k][size-1-l] != buff[j+k][saikobi-l]:
                                count = 0
                                break
                        if count == 0:
                            break
                    else:
                        print(j,saikobi-C+1)
                    saikobi += 1  
                    
            

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


bm_search(pattern, buff)

Submission status: Wrong Answer

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]:
                count += 1
                table[i] = count
                j += 1
        else:
            count = 0
            j = 0
            table[i] = 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 j == pl-1:
                x = buffplace - j
                bfs(pattern,buff,x,y)
                buffplace -= j - 1
                j = 0
            if pattern[0][j] != buff[y][buffplace]:
                buffplace += 1
            elif pattern[0][j] == buff[y][buffplace]:
                buffplace += 1
                j += 1
            else:
                j = table[j] - 1
            
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: Wrong Answer

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]:
                count += 1
                table[i] = count
                j += 1
        else:
            count = 0
            j = 0
            table[i] = 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 j == pl:
                x = buffplace - j
                bfs(pattern,buff,x,y)
                buffplace -= j - 1
                j = 0
            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 
            
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: Wrong Answer

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] = 0
            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: Wrong Answer

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 - c:
        print(i//w, i%w)

Submission status: Wrong Answer

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 - c or i//w == h - r):
        print(i//w, i%w)

Submission status: Wrong Answer

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

prog = re.compile(p)
iter = prog.finditer(f)
for match in iter:
    i = match.start()
    print(i//w, i%w)

Submission status: Wrong Answer

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
l_f = len(f)

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)

Submission status: Wrong Answer

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))
    if R > C:
        H, W = W, H
        MAP = tuple("".join(a) for a in zip(*MAP))
        R, C = C, R
        PTN = tuple("".join(a) for a in zip(*PTN))
    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: Wrong Answer

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))
    flg = True
    if R > C:
        flg = False
        H, W = W, H
        MAP = tuple("".join(a) for a in zip(*MAP))
        R, C = C, R
        PTN = tuple("".join(a) for a in zip(*PTN))
    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 = []
    if flg:
        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}")
    else:
        for j in range(H - R + 1):
            if PTN[0] not in MAP[j]:
                continue
            for i in range(W - C + 1):
                if solve(j, i):
                    ans.append(f"{i} {j}")
    if ans:
        if flg:
            print("\n".join(a for a in ans))
        else:
            print("\n".join(a for a in ans[::-1]))
MAIN()

Submission status: Time Limit Exceeded

Solution code:
def check(r,c):
    flag = True
    for ri,rj in enumerate(B):
        for ci,cj in enumerate(rj):
            if not A[ri+r][ci+c] == cj:
                flag = False
                break
    return flag

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)]

for r in range(H-R+1):
    for c in range(W-C+1):
        if check(r,c):
            print(r,c)

Submission status: Time Limit Exceeded

Solution code:
def check(r,c):
    return True if B == [i[c:c+C] for i in A[r:r+R]] else False

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)]

for r in range(H-R+1):
    for c in range(W-C+1):
        if check(r,c):
            print(r,c)

Submission status: Time Limit Exceeded

Solution code:
def get_common(string,len_string):
    common_length=[0]*len_string
    tmp=0
    tmp_tmp=0
    for i in range(1,len_string):
        if(string[i]==string[tmp]):
            tmp_tmp=tmp
            while(string[i]==string[tmp_tmp] and tmp_tmp >0):
                tmp_tmp=common_length[max([tmp_tmp-1,0])]
            common_length[i-1]=tmp_tmp
            tmp+=1
        else:
            common_length[i-1]=tmp
            while(string[i]!=string[tmp] and tmp>0):
                tmp=common_length[max([tmp-1,0])]
            if(string[i]==string[tmp]):
                tmp+=1

    if(string[-1]==string[tmp-1]):
        common_length[-1]=tmp
    common_length[0]=0
    return common_length



def find_str(field,field_row,pattern,common_length,H,W,h,w):
    tmp=0
    column_list=[]
    len_pattern=len(pattern[0])
    for i in range(len(field[field_row])):
        if(field[field_row][i]!=pattern[0][tmp]):
            while(field[field_row][i]!=pattern[0][tmp] and tmp>0):
                tmp=common_length[0][max([tmp-1,0])]
            if(field[field_row][i]==pattern[0][tmp]):
                tmp+=1
        else:
            tmp+=1
            if(tmp==len_pattern):
                column_list.append(i-tmp+1)
                tmp=common_length[0][-1]
    
    
    
    for j in range(1,h):
        tmp=0
        loop=0
        while( loop  <len(column_list)):
            column=column_list[loop]
            if(loop < len(column_list) -1):
                next_column=column_list[loop+1]
            else:
                next_column=len(field[0])+len(pattern[0])+1#十分でかけりゃ何でも良い
            ini_tmp=tmp
            for i in range(0,len_pattern+1):
                if(field[field_row+j][column+ i+ini_tmp]!=pattern[j][tmp]):
                    if(column + i + ini_tmp < next_column):
                        tmp=0
                        column_list.pop(loop)
                        break
                    else:
                        while(tmp>column+i+ini_tmp-next_column):
                            tmp=common_length[j][max([tmp-1,0])]
                        if(tmp!=column+i+ini_tmp-next_column ):
                            tmp=0
                        column_list.pop(loop)
                        break
                else:
                    tmp+=1
                    if(tmp==len_pattern):
                        if(column + i + ini_tmp < next_column ):
                            tmp=0
                            loop+=1
                            break
                        else:
                            while(tmp>column+i+ini_tmp-next_column+1):
                                tmp=common_length[j][max([tmp-1,0])]
                            if(tmp!=column+i+ini_tmp-next_column+1):
                                tmp=0
                            loop+=1
                            break
    for column in column_list:
        print(f"{field_row} {column}")










H,W=map(int,input().split())
field=[]
for i in range(H):
    field.append(input())
h,w=map(int,input().split())
pattern=[]
for i in range(h):
    pattern.append(input())

common_length=[]
for i in range(h):
    common_length.append(get_common(pattern[i],w))

for i in range(H-h+1):
    find_str(field,i,pattern,common_length,H,W,h,w)

Submission status: Time Limit Exceeded

Solution code:
def get_common(string,len_string):
    common_length=[0]*len_string
    tmp=0
    tmp_tmp=0
    for i in range(1,len_string):
        if(string[i]==string[tmp]):
            tmp_tmp=tmp
            while(string[i]==string[tmp_tmp] and tmp_tmp >0):
                tmp_tmp=common_length[max([tmp_tmp-1,0])]
            common_length[i-1]=tmp_tmp
            tmp+=1
        else:
            common_length[i-1]=tmp
            while(string[i]!=string[tmp] and tmp>0):
                tmp=common_length[max([tmp-1,0])]
            if(string[i]==string[tmp]):
                tmp+=1

    if(string[-1]==string[tmp-1]):
        common_length[-1]=tmp
    common_length[0]=0
    return common_length



def find_str(field,field_row,pattern,common_length,H,W,h,w):
    tmp=0
    column_list=[]
    len_pattern=len(pattern[0])
    for i in range(len(field[field_row])):
        if(field[field_row][i]!=pattern[0][tmp]):
            while(field[field_row][i]!=pattern[0][tmp] and tmp>0):
                tmp=common_length[0][max([tmp-1,0])]
            if(field[field_row][i]==pattern[0][tmp]):
                tmp+=1
        else:
            tmp+=1
            if(tmp==len_pattern):
                column_list.append(i-tmp+1)
                tmp=common_length[0][-1]
    
    
    
    for j in range(1,h):
        tmp=0
        loop=0
        while( loop  <len(column_list)):
            column=column_list[loop]
            if(loop < len(column_list) -1):
                next_column=column_list[loop+1]
            else:
                next_column=len(field[0])+len(pattern[0])+1#十分でかけりゃ何でも良い
            for i in range(0,len_pattern+1):
                if(field[field_row+j][column+ i]!=pattern[j][i]):
                    tmp=0
                    column_list.pop(loop)
                    break
                else:
                    tmp+=1
                    if(tmp==len_pattern):
                        tmp=0
                        loop+=1
                        break

    for column in column_list:
        print(f"{field_row} {column}")










H,W=map(int,input().split())
field=[]
for i in range(H):
    field.append(input())
h,w=map(int,input().split())
pattern=[]
for i in range(h):
    pattern.append(input())

common_length=[]
for i in range(1):
    common_length.append(get_common(pattern[i],w))

for i in range(H-h+1):
    find_str(field,i,pattern,common_length,H,W,h,w)

Submission status: Time Limit Exceeded

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

for i in range(th - ph + 1):
    for j in range(tw - pw + 1):
        for k in range(ph):
            if t[i + k][j:j + pw] != p[k]:
                break
        else:
            print(i, j)

Submission status: Time Limit Exceeded

Solution code:
th, tw = map(int, input().split())
t = [input().strip() for _ in range(th)]
ph, pw = map(int, input().split())

t = [[t[i][j:j + pw] for j in range(tw - pw + 1)] for i in range(th)]
p = [input().strip() for _ in range(ph)]

for i in range(th - ph + 1):
    for j in range(tw - pw + 1):
        for k in range(ph):
            if t[i + k][j] != p[k]:
                break
        else:
            print(i, j)

Submission status: Time Limit Exceeded

Solution code:
import string

char_dict = {c: i for i, c in enumerate(string.digits + string.ascii_letters)}

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


def conv_str(s):
    result = 0
    for c in s:
        result <<= 6
        result += char_dict[c]
    return result


t = [[conv_str(t[i][j:j + pw]) for j in range(tw - pw + 1)] for i in range(th)]
p = [conv_str(input().strip()) for _ in range(ph)]

for i in range(th - ph + 1):
    for j in range(tw - pw + 1):
        for k in range(ph):
            if t[i + k][j] != p[k]:
                break
        else:
            print(i, j)

Submission status: Time Limit Exceeded

Solution code:
from hashlib import md5

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

t = [[md5(t[i][j:j + pw].encode('utf-8')).digest() for j in range(tw - pw + 1)] for i in range(th)]
p = [md5(input().strip().encode('utf-8')).digest() for _ in range(ph)]

for i in range(th - ph + 1):
    for j in range(tw - pw + 1):
        for k in range(ph):
            if t[i + k][j] != p[k]:
                break
        else:
            print(i, j)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
T = [input() for i in range(H)]
R, C = map(int, input().split())
P = [input() for i in range(R)]

def match(ox, oy):
	for y in range(R):
		for x in range(C):
			if T[oy + y][ox + x] != P[y][x]:
				return False
	return True

for y in range(H - R + 1):
	for x in range(W - C + 1):
		if T[y][x] == P[0][0]:
			if match(x, y):
				print("{0} {1}".format(y, x))

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8

def PS(A,B,H,W,R,C):
    for i in range(H):
        for j in range(W):
            if A[i][j]==B[0][0]:
                ans=0
                for k in range(R):
                    for l in range(C):
                        if i+k<H and j+l<W and A[i+k][j+l]==B[k][l]:
                            ans+=1
                if ans==R*C:
                    print(i,j)

if __name__=="__main__":
    H,W=map(int,input().split(" "))
    A=[]
    for i in range(H):
        A.append(list(input()))
    R,C=map(int,input().split(" "))
    B=[]
    for i in range(R):
        B.append(list(input()))
    PS(A,B,H,W,R,C)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int,input().split())
A = []
for i in range(H):
    A.append(input())
R, C = map(int,input().split())
B = []
for i in range(R):
    B.append(input())
    
for i in range(H-R + 1):
    for k in range(W-C +1):
        count = 0
        for j in range(R):
            if B[j] == A[i+j][k:k+C]:
                count += 1
            else:break
        if count == R:
            print(i,k)

Submission status: Time Limit Exceeded

Solution code:
CSIZE = 256

def make_bm_table(pattern,size):
    bm_table = [size]*CSIZE
    for i in range(size):
        dist = size-i-1
        charac = pattern[i]
        bm_table[ord(charac)] = dist
    return bm_table

def bm_search(pattern,buff): 
        size = C
        bm_table = make_bm_table(pattern[0], size)    
        buffsize = W
        for j in range(H-R+1):
            saikobi = size-1
            while saikobi < buffsize:
                for i in range(size):
                    if pattern[0][size-i-1] != buff[j][saikobi-i]:
                        saikobi += max(bm_table[ord(buff[j][saikobi-i])]-i,1)
                        break
                else:
                    count = 1
                    for k in range(1,R):
                        for l in range(C)[::-1]: 
                            if pattern[k][size-1-l] != buff[j+k][saikobi-l]:
                                count = 0
                                break
                        if count == 0:
                            break
                    else:
                        print(j,saikobi-C+1)
                    saikobi += 1  
                    
            

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


bm_search(pattern, buff)