Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

Fear_Is_An_Illusion's blog

Best method to find number of times a 2D pattern occurs in a matrix ?
By Fear_Is_An_Illusion, history, 11 years ago, In English

pattern is fixed

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can you give an example ?

→ Reply
  • »
    »
    11 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    matrix

    a b o z q
p z q 1 3
p 1 3 z q
a b c d e

    pattern

    z q 
1 3

    verdict : yes, 2 times

    → Reply
    • »
      »
      »
      11 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      is overlapping allowed ?

      For example :

      a a a a a

      a a a a a

      a a a a a

      pattern

      a a

      a a

      Should the answer be 2 or 8?

      → Reply
      • »
        »
        »
        »
        11 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        lets not allow it :P

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, hide # ^ |
          ← Rev. 3  
          Vote: I like it 0 Vote: I do not like it

          maybe slow solution. nP, mP — sizes of pattern. let's say position(i, j) is good if patern occurs in it. between every 2 good positions (i, j) and (i2, j2) add edge if rectangles (i, j, i + nP — 1, j + mP — 1) and (i2, j2, i2 + nP — 1, j2 + mP — 1) are intersect. Now problem is: given graph, find max subset of verticles, such that there r no 2 verticles u, v in this subset such that u, v are connected by edge. It's well known problem.

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it

            I think it's even slower than the brute force, since maximal independent set is NP-Hard... or did i get something wrong?

            → Reply
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
11 years ago, hide # |
← Rev. 4  
Vote: I like it -19 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Your obvious solution has a big complexity, which's definitely not what he needed.

    → Reply
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Take a look at KMP algorithm.

→ Reply