Suffix Tree using Ukkonen's algorithm

Construct suffix tree using Ukkonen's algorithm which is linear time algorithm

[yashvaibhav]

Timestamps for the video: (will be edited as I follow along)
0:00 - 10:10 : Dry Run of rules on example string
10:11 - 12:52 : Optimization to reduce complexity
12:52 - 14:58 : Suffix Links
14:58 - 22:15 : Active Points
22:15 - : Exemplar build of Suffix Tree

[worthsparks]

I've been struggling with this algorithm for a while now. Your video is the perfect complement to Dan Gusfield's 1997 book, which describes the algorithm in detail. Given the choice, I would highly recommend your video over the book's description. Well done. I think I've got it now. Thanks.

[DarshanWashimkar]

This is the best video for "Suffix tree" on YouTube. It's going to my library. Thanks for the Video.

[ketan_sahu]

The only source that explained me suffix tree in simple English and good examples. Thanks

[priyadarshikunal]

I never read this topic and suddenly needed the explanation in an hour and this one is just helped.
Thanks for putting this up.

[kevinbanker]

Great job, Tushar Roy! I spent many tough hours not understanding the algorithm and then, I finally found this brilliant video! Two examples made it really really clear! POY man, keep up the great work!

[kibojiyuu]

Thank you soooo much! You are an amazing human being for spending all this time to make this lengthy video to help others! I have no words! Thank you thank you thank you and I wish the best to you and your family! You deserve everything you wish for! Thank you!

[AbhishekTiwarics]

Great explanation ....
One confusion... At 31:20 .. you told that after creating internal node .. we increase active edge by 1 and decrease active len by 1 and then traversed the tree... While at 52:10 .. you just decreased active len by 1 but did not increase active edge by 1 before traversing ... Why ?

[jolgiiis]

Tushar Roy, saving my sorry ass once more! This guy is the MVP of IT on youtube!

[shreyjain]

At 20:23 the extension of path b should start from node C. And travelling on suffix link we then land up on node D.

[AnandKumar-nxke]

At 40:35 while creating node Q you told when leaf node is created then remaining is reduced by one then why that has not been done

[sanjeevacham]

Thank Tushar, it is a great explanation. I don't have words to praise you.

[andy]

This is beautiful. Thank you very much for the best explanation of this algorithm on the internet. :-)

[CavelordVerdusk]

Thanks for the great explanation, but I have a question.


On 21:00, shouldn't you traverse the link on D to E, rather than B to root, considering D happens to already has a suffix link? It'll make the amount of edges you have to traverse less.

[subhankarroy]

This video is very helpful to understand suffix tree formation in linear time.
Many many thanks sir :)

[ferg]

Chea Uce this is a great video. I love the time you put into making this :) :) much appreciated!

[Hadrhune]

Really cool video, helped me recap and seeing the algorithm through its various iterations.

[padamcaco]

Excellent video explaining a complex algorithm.

Great energy going through the steps and running through all the states at each step.

1 feedback: For drawing internal nodes you could have done it without switching off the recording.
I still understand it. just thought of pointing it out.

I still miss on the spirit & big insight that helped Ukkonen arrive at this algorithm (I have a sense of it but havent fully discovered it. Need to watch video again).

[duongkstn]

thanks for the elegant and clear explanation

[gnvenky]

Thanks Tushar! Great explanation making the algorithm understanding easy