Does anyone have a solution to this problem, even just for part b?

The question is basically (for the highest sub-task) that you have to decode a length 1000 binary string, and you have 1024 queries of the form "is substring S present", on which an answer of Yes or No will be given.

Thanks!