5k_sync_closer's blog

By 5k_sync_closer, history, 7 weeks ago, In English

My IP has been banned from luogu for some reason, so I'm asking this question on CF.

Question:

If string S and T with same length has $$$k$$$ or less different characters, we say S matches T,

then if A and B are given, how to find every substring of A that matches B?

My English is poor, so there would be some grammar mistakes, but I think u can understand what I mean.

I don't need trivial solutions such as $$$O(n^2)$$$ (brute) or $$$O(nk\log n)$$$ (hash) or $$$O(\dfrac{n^2\Sigma}w)$$$ (bitset, probably not faster than brute).

Full text and comments »

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

By 5k_sync_closer, history, 10 months ago, In English

The problems are low-quality and copied from somewhere.

Full text and comments »

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