The Grid Search

question

Given a 2D array of digits, try to find the occurrence of a given 2D pattern of digits. For example, consider the following 2D matrix:

1234567890  
0987654321  
1111111111  
1111111111  
2222222222  
Assume we need to look for the following 2D pattern:

876543  
111111  
111111
If we scan through the original array, we observe that the 2D pattern begins at the second row and the third column of the larger grid (the  in the second row and third column of the larger grid is the top-left corner of the pattern we are searching for).

So, a 2D pattern of  digits is said to be present in a larger grid , if the latter contains a contiguous, rectangular 2D grid of digits matching with the pattern , similar to the example shown above.

Input Format

The first line contains an integer, , which is the number of test cases.  test cases follow, each having a structure as described below: 
The first line contains two space-separated integers,  and , indicating the number of rows and columns in the grid , respectively. 
This is followed by  lines, each with a string of  digits, which represent the grid . 
The following line contains two space-separated integers,  and , indicating the number of rows and columns in the pattern grid . 
This is followed by  lines, each with a string of  digits, which represent the pattern .

Constraints

 
 
 

Output Format

Display 'YES' or 'NO', depending on whether (or not) you find that the larger grid  contains the rectangular pattern . The evaluation will be case sensitive.

Sample Input

2
10 10
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
3 4
9505
3845
3530
15 15
400453592126560
114213133098692
474386082879648
522356951189169
887109450487496
252802633388782
502771484966748
075975207693780
511799789562806
404007454272504
549043809916080
962410809534811
445893523733475
768705303214174
650629270887160
2 2
99
99
Sample Output

YES
NO

solution

#!/bin/ruby

t = gets.strip.to_i
for a0 in (0..t-1)
  
    rr, cc = gets.strip.split(' ')
    rr = rr.to_i
    cc = cc.to_i
    s1 = []
    for i in (0..rr-1)
        s1 << gets.strip
    end
  
    r,c = gets.strip.split(' ')
    r = r.to_i
    c = c.to_i  
    s2 = []
    for i in (0..r-1)
        s2 << gets.strip
    end
  
  
    found = false

    s1.each_with_index { |i, index|   
        s2_c = 0
        next if !found and !(i[s2[s2_c]])
      
        prev_pos = 0
        first = true
        j = index
        while (s2_c != s2.size) 
         
          #puts "pos #{pos}"
          pos = s1[j].index(s2[s2_c], prev_pos)
          
          break unless pos
          
          if first or pos == prev_pos
            first = false
            s2_c += 1
            j += 1
          else
            first = true
            j = index
            s2_c = 0
          end
          prev_pos = pos
        end
      
      
        if s2.size == (j - index)
          found = true   
          break
        end
    
    }
  
  puts found ? "YES" : "NO"
 end