I’d like to ask a question about String Query problem.
I wanted to solve it as:
- I’m maintaining 2 double ended queues (l and r - left and right part of actual text) to perform insert and delete operations in O(1)
- when there is query, I perform Aho-Corasick algorithm to find number of ocurences in text
I know that AC is used for multiple strings matching, I just wanted to try it.
I’d like to ask:
- is complexity of this solution good enought to pass in TL?
- may someone help me to find error in my solution? http://www.codechef.com/viewsolution/2042887
I hope everything is clear in code - f is fail function, fs is flag array that contains information if fail function is calculated already (I used lazy calculation) and q is query string…