Please help me finding the indices as well

#1

I have tried solving this for input string arr[] = {“he”, “she”, “hers”, “his”}; string text = “ahishers”; but got wrong ans because characters are repeating. Please help me out finding the indices of all the strings.

#2

Hi Raj,
ending node of every substring is unique!,
so answer is from ed-string_length+1 to ed (and not from st to ed).
refer this update-

#3

okay got it thanks. And one more thing https://www.geeksforgeeks.org/aho-corasick-algorithm-pattern-searching/ . is this the same algorithm ??

#4

One more thing, Why you have incremented the ind value after if statement. line no. 33 , in my code I have done like curr->index=ind++ (line no. 30) but this is giving wrong answer but you have increment it on line 33 it is giving right ans? Why is that??

#5

Raj you must update the index as you move to next character in string (but you were updating only when new node if formed, resulting in incorrect indexing)!

#6

This is even better!, its actually O(n).

#7

O(N) , it is quite interesting. Can you help me understanding the approach??

#8

Hi Raj, this may be helpful https://cp-algorithms.com/string/aho_corasick.html