Algoritma - Başka bir 2d dizisinde 2d dizisinin varlığını bulun

Question

Bir röportajda bu soruya rastladım ve bunu yapmanın en iyi yolunu bulamıyorum.

Sorunun, iki tane 2d dizisi var, biri diğerinden daha büyük. burada Dizi 2 Dizi 1, algo gerçek dönmelidir içeren, beri, demek

Array_1 = [[1,2], 
      [5,6]] 

ve

Array_2 = [[1,2,3,4], 
      [5,6,7,8], 
      [9,10,11,12]] 

sağlar. Aksi halde, yanlış.

Dizinin boyutu herhangi bir şey olabilir.

Answer 1

Ben boş değerlerle büyük boyutlara küçük dizideki doldururdu

(veya NaN) ile gereksiz boş değerlere şerit/1D dönüştürmek ve kesecek:

array_1 = [1, 2, null, null, 5, 6] 
array_2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] 

sonra, 1D dizileri karşılaştırma boş değerler atlama yaparken - bu en kötü durumda O(n*m) olacaktır (örneğin [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] karşı [1,1,1,2] gibi) Ve (daha büyük dizideki her sayı farklı olsaydı) en iyi durumda O(n) olacağını

Düzenleme: Daha fazla mantık değil satırlar arasında, sadece daha büyük dizinin tam satırlar içinde karşılaştırma sağlamak için gereklidir. ..

---

Ben

---

Ayrıca döndürmek olabilir ... Eğer pozisyonların sözlüklere diziler dönüştürmek ve çoklu karşılaştırma yapmak gerekirse biraz daha karmaşık ve daha hızlı bir algoritma anlamaya sanırım gerekirse daha küçük dizi, örneğin .:

array_1_270 = [6, 2, null, null, 1, 5] 

Answer 2

Bunu deneyin. Daha küçük dizi büyük dizi içinde döndürüldüğünde ise bu uyuşmadığını

function Test() { 

var x = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]; 
var y = [[6, 7], [10, 12]]; 

for (i = 0; i < x.length; i++) { 
    for (j = 0; j < x[i].length; j++) { 
     if (x[i][j] == y[0][0]) 
      if (findMatch(x, y, i, j)) { 
       console.log("Match Found"); 
       return true; 
      } 
    } 
} 
console.log("Not found"); 
return false; 
} 


function findMatch(x, y, i, j) { 
var b = true; 
for (k = i; k < y.length; k++) { 
    for (n = j; n < y[k].length; n++) { 
     if (y[k - i][n - j] != x[k][n]) { 
      b = false; 
      break; 
     } 
    } 
} 
return b; 
} 

Not. (JavaScript ile yazılan)

Answer 3

2 boyut için aho-corasick algoritmasını deneyebilirsiniz. Aho-corasick algoritması en hızlı çoklu model eşleştirmesidir. İşte benzer bir soru: is there any paper or an explanation on how to implement a two dimensional KMP?

Answer 4

Belki biraz daha basit Python 2,6

def check(): 
    small=[[1,2],[5,6]]    #matches upper left corner 
    smallrows = len(small)   #rows = 2 
    smallcols = len(small[0])  #cols = 2 
    big=[[1,2,3,4],[5,6,7,8],[9,10,11,12]] 
    bigrows = len(big)    #rows = 3 
    bigcols = len(big[0])   #cols = 4 

    for i in range(bigrows-smallrows+1):  #i is number row steps 
     for j in range(bigcols-smallcols+1): #j is number col steps 
      flag = 0 
      for k in range(smallrows): 
       for l in range(smallcols): 
        if big[i+k][j+l] != small[k][l]: 
         flag = 1 
         continue 
      if flag == 0: 
       return(True) 
    return(False) 

print check()