Блог пользователя Fear_Is_An_Illusion

Best method to find number of times a 2D pattern occurs in a matrix ?
Автор Fear_Is_An_Illusion, история, 11 лет назад, По-английски

pattern is fixed

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
11 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can you give an example ?

→ Ответить
»
11 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Use hashes, just like when you find a substring in a string. Can't write more details now.

→ Ответить
  • »
    »
    11 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Convert each row of your pattern to a single hash value. If your patter has row length = n, then convert every substring of length n in each row of your matrix to a single hash value.

    Now the problem is to find a substring in a string along the columns for which you can use KMP or hashes again.

    → Ответить
»
11 лет назад, скрыть # |
← Rev. 4  
Проголосовать: нравится -19 Проголосовать: не нравится

Lets assume the array is of size N1*M1 and the pattern is of size N2*M2 1<=N2<=N1<=M2<=M1<=1000000 && N1*M1<=1000000 && N2*M2<=1000000.

We are not consider overlaps.

You need a visited array to make sure that you don't count overlaps and avoid checking a row and column more than once.

for(int i=0;i<=(n1-n2);i++){
    for(j=0;j<=(m1-m2);j++){
        if(!vis[i][j]){
           answer+=checkPattern(i,j); 
        }
    }
}

In check pattern , we'll return 0 if the pattern starting from i,j does not match. Else if it matches, we'll mark all the pattern matching cells as visited and return 1.

Update : Please let me know what is wrong guys.

→ Ответить
»
11 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Take a look at KMP algorithm.

→ Ответить