Aho-Corasick: Shortest word ending on certain position

2018-10-22 18:09:21

I need to create an algorithm which's output is for every position an index of position and shortest word, that ends here.

Now I did it with complexity O(P + S + O), where P is number of patterns, S length of string we search in and O number of occurences. But I need to do it without the number of occurences in the complexity.

I imagine that for every state of the automaton where we would normally report occurence, we jump back using the "dictionary suffix links" (not sure about the term as I am not studying in English) as far as we can. Then the state we end in is a state where we would normally report occurence of a word, which is the shortest. But by jumping as far as I can using every "dictionary suffix link" could end up with the complexity I have mentioned. How to construct direct "dictionary suffix link" to the shortest word during the construction of the automaton using Aho-Corasick?

Edit: Also, how could I easily deduce an algorithm with shortest word but sta