editorials are not much helpful , so please help and explain from scratch
This question can be solved using Rabin Karp + Segment Tree .
Store hash and reverse hash of the string , and keep track of it using Segment tree.
One can collaborate the idea of hashing with segment trees and make something called Dynamic String Hashing. Along with segment trees accompanied by lazy propagation, the following problem can be reduced to
O(log(n)) per query.
You can get idea of Rabin Karp from here . I myself understood the concept from here , and solved this question in the contest .
After you understand the approach from the blog , you can refer to my submission here .