String Query - WA

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:

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…

1 Like