Qualified's blog

By Qualified, history, 4 years ago, In English

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)

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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