Блог пользователя Qualified

Автор Qualified, история, 4 года назад, По-английски

The title prolly ain't clear at all. You are given a string $$$s$$$ and a string $$$t$$$. For every substring $$$s$$$ of length $$$|t|$$$, you are to find the number of different characters between the substring of $$$s$$$ and $$$t$$$ in $$$O(n \cdot log(n))$$$ or less. It is guaranteed that $$$|t| \le |s|$$$.

Example: s: abac t: ag output: [1, 2, 1]

s: adfjaasd t: asdf output: [3, 4, 4, 4, 3]

Don't just downvote, tell me where I should improve or what the answer to my question is. Pls, my contribution is already too low (-75).

Problem statement: 1196D2 - RGB Substring (hard version)

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can be done using Z- algorithm, create the augmented string like ag#abac for the given example, and then just check the longest prefix for each substring

»
4 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

I think you should probably mention the source of the problem. People aren't likely to help if they might be helping you cheat in an ongoing contest.

I don't know a popular way to count mismatch characters on substrings besides FFT or BitSets (alphabet*N*log(N) or alphabet*N/64). I think you might be able to google those (or I can explain it if I know it's from a completed contest). If you wanna google it, try 'FFT string matching'

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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