pattern is fixed
# | User | Rating |
---|---|---|
1 | tourist | 3880 |
2 | jiangly | 3669 |
3 | ecnerwala | 3654 |
4 | Benq | 3627 |
5 | orzdevinwang | 3612 |
6 | Geothermal | 3569 |
6 | cnnfls_csy | 3569 |
8 | jqdai0815 | 3532 |
9 | Radewoosh | 3522 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | adamant | 156 |
4 | maroonrk | 153 |
5 | -is-this-fft- | 148 |
5 | atcoder_official | 148 |
5 | SecondThread | 148 |
8 | Petr | 147 |
9 | nor | 144 |
9 | TheScrasse | 144 |
pattern is fixed
Name |
---|
Can you give an example ?
matrix
pattern
verdict : yes, 2 times
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?
lets not allow it :P
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.
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.
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.