will this suffice? here
What as the O(N^1.5) solution?
@wjmzbmr: Do you mean N=the length of S (or the number of operations performed) or N=the total length of the query strings ? I am curious because one of my initial attempts tried to achieve O(sqrt(total length of the query strings)) per each operation (inserts, deletes, queries) on average. My idea was to keep counts of āsmallā query strings and to use KMP on the whole of S for ālargeā query strings (the threshold between āsmallā and ālargeā was about sqrt(total length of query strings)). But this turned out to be too slow (but I used STL maps for the counts which increased the complexity).
@mugurelionut both can pass.
I have tried the sqrt(total length of query strings) in testing, but it seems I lack of optimization skills, it run very slow. so I just make the TL a bit tight.
I think that is too slow.
@wjmzbmr,can you please tell me what was your expected data structure(rope/generalised suffix tree/extended suffix array) and please give us tutorial for STRQUERY.
To all: My answer was considerably updated.
So, just to see if I got things rightā¦ Does the official solution work in the ONLINE mode ? (i.e. it can process a new operation as soon as it reads it) I think many of the AC solutions (mine included) only work in the OFFLINE case (in my solution I initially construct a trie of all the query strings from the input file), so an ONLINE solution would be quite interesting.
@mugurelionut yes.It could be even extended to something like āhow many times does string q occur in s after the k-th operation?ā in online mode.
the tutorial is written by anton_lunyov, it will become available soon.
read my comment ā¦ was getting problemā¦ i think dynamic allocation is the problem
@wjmzbmr: I seeā¦ So you can also keep the history/versions of the data structure thenā¦ Well, I canāt wait for the editorial, then. In case you based your solution on some papers/tutorials available online (e.g. like the paper suggested by @cyberax), then some links to them would also be appreciated.
I didnāt think on history/versions so donāt expect this in the editorial 
And I donāt know about papers/tutorials that contain this approach.
@anton_lunyov : i am waiting for your tutorial eagerly.
i tried to solved this problem using simple approach but unfortunately was getting WA.I checked the output with my custom test case set with the AC solutions but mine and their output were same.
here is my code link(used KMP algo to count occurrence ):-
http://www.codechef.com/viewsolution/2024390
It would be great if you can find error in my code or check it against your custom test case set and let me know.
Thanks in Aadvance
@anton_lunyov: Yes, no problem about history/versions Maybe @wjmzbmr can mention his own ideas (or hints) regarding history/versions after the editorial is published.