5k_sync_closer's blog

A string matching problem
By 5k_sync_closer, history, 2 months 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).

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

»
2 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Auto comment: topic has been updated by 5k_sync_closer (previous revision, new revision, compare).

→ Reply
»
2 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Auto comment: topic has been updated by 5k_sync_closer (previous revision, new revision, compare).

→ Reply
»
2 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Just check if B has $$$\leqslant k$$$ distinct characters. If yes — the answer is $$$\max(0, |S| - |T| + 1)$$$, if no — the answer is $$$0$$$. This is $$$O(n \log n)$$$ or $$$O(n)$$$ depending on your computational model and implementation.

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    'k or less different characters' means ones between A and B

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      are you asking for how many substrings in A match B or how many substrings in A matching the opposing substring in B ?

      → Reply
»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

can you describe the bitset solution in details ?

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Find every substring $$$S$$$ of length $$$|B|$$$ in A,for each letter $$$c$$$(from a to z) extract the bitset of the $$$c$$$'s occurrence in $$$S$$$ and in $$$B$$$, then count bits that is $$$1$$$ in $$$S$$$'s bitset and is $$$0$$$ in $$$B$$$'s.

    → Reply
»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

OK now I know the solution: FFT. $$$O(n\Sigma\log n)$$$.

but I gtg so goodbye

→ Reply