Suffix Trees

In the Suffix Links construction, it is mentioned that for the internal node created (as a result of RULE 2) during the jth extension of the ith phase got it’s suffix link during the next extensions of this ith phase only. (i.e. by the end of the ith phase we have the suffix links for all the internal nodes created so far).

But during the next extension (i.e in (j+1)th) if we have to apply RULE 3 then we are going to stop the current phase and move on to the next phase directly.

So, my doubt is suppose we have created an internal node after applying RULE 2 in the jth extension and in the very next extension of the current phase we get RULE 3 (and let us suppose that we are not ending on a node in this case i.e. we have out required string in middle of some edge). So, how the suffix link for the internal node created during the previous phase got created? I think I am missing something. Please help me!

Thanks in advance :slight_smile:

1 Like