Editorial for Mock CCC '22 2 S3 - Kaguya Wants to Analyze the Academy Anthem

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

This problem can be solved with a suffix array online. Alternatively, using Rabin-Karp, compute for each length of query string that appears (there can be at most $\mathcal{O}(\sqrt{|s|})$ ~\mathcal{O}(\sqrt{|s|})~ hashes of all substrings of that length and answer queries offline.

Comments

There are no comments at the moment.