### Fear_Is_An_Illusion's blog

By Fear_Is_An_Illusion, history, 7 years ago, pattern is fixed Comments (11)
| Write comment?
 » Can you give an example ?
•  » » 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
•  » » » 7 years ago, # ^ | ← Rev. 2 →   is overlapping allowed ? For example : a a a a aa a a a aa a a a apattern a a a a Should the answer be 2 or 8?
•  » » » » lets not allow it :P
•  » » » » » 7 years ago, # ^ | ← Rev. 3 →   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.
•  » » » » » » I think it's even slower than the brute force, since maximal independent set is NP-Hard... or did i get something wrong?
 » Use hashes, just like when you find a substring in a string. Can't write more details now.
•  » » 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.
 » 7 years ago, # | ← Rev. 4 →   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.
•  » » Your obvious solution has a big complexity, which's definitely not what he needed.
 » Take a look at KMP algorithm.