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)
Auto comment: topic has been updated by Qualified (previous revision, new revision, compare).
Auto comment: topic has been updated by Qualified (previous revision, new revision, compare).
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
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'
1196D2 - RGB Substring (hard version). I was trying to solve this problem. Updated blog.
Auto comment: topic has been updated by Qualified (previous revision, new revision, compare).
Auto comment: topic has been updated by Qualified (previous revision, new revision, compare).
Auto comment: topic has been updated by Qualified (previous revision, new revision, compare).