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: Runtime Error

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
        for loop in range(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
                            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
                            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: Runtime Error

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())
    
b = B[0]
b_for_move = [0 for i in range(len(B))]

for i in range(len(b)):
    for j in range(0,len(b)-i)[::-1]:   
        if b[i:i+j] == b[len(b)-j-1:len(b)]:
            b_for_move[i] = j
            break
    else: b_for_move[i] = 1
    
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:
                i += b_for_move[j] -1
                break
        if count == R:
            print(i,k)

Submission status: Runtime Error

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

b = B[0]
b_for_move = [0 for i in range(len(b))]

for i in range(len(b)):
    for j in range(0,len(b)-i)[::-1]:   
        if b[i:i+j] == b[len(b)-j-1:len(b)]:
            b_for_move[i] = j
            break
    else: b_for_move[i] = 1
    

        
         
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:
                i += b_for_move[j] -1
                break
        if count == R:
            print(i,k)

Submission status: Runtime Error

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 = R
        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+2)
                    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: Runtime Error

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: Runtime Error

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 = (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: WA: Presentation Error

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}")
    print(*ans, sep="\n")
MAIN()