pattern is fixed

# | User | Rating |
---|---|---|

1 | tourist | 3803 |

2 | Benq | 3783 |

3 | Radewoosh | 3602 |

4 | maroonrk | 3575 |

5 | fantasy | 3526 |

6 | ko_osaga | 3500 |

7 | ksun48 | 3491 |

8 | Um_nik | 3486 |

9 | jiangly | 3474 |

10 | orzdevinwang | 3461 |

# | User | Contrib. |
---|---|---|

1 | awoo | 180 |

2 | -is-this-fft- | 177 |

3 | nor | 169 |

4 | Um_nik | 168 |

5 | SecondThread | 164 |

6 | maroonrk | 163 |

7 | adamant | 161 |

8 | kostka | 160 |

9 | YouKn0wWho | 158 |

10 | errorgorn | 153 |

pattern is fixed

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/06/2023 08:42:06 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

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.