16. Strings

MIT 6.851 Advanced Data Structures, Spring 2012
Instructor: Erik Demaine

Strings: suffix tree, suffix array, linear-time construction for large alphabets, suffix tray, document retrieval

License: Creative Commons BY-NC-SA

[ScipioWasHere]

TFW he asks why then gives the answer and giggles, and I giggle along with him but am still clueless.

[dhruvjoshi]

how does j-i th weighted ancestor of str[i:] gives all occurences of str[i:j], I don't get it, someone please help me with this.

[videofountain]

Thanks. I am impressed with the clarity of the video.  Notable improvement. 

[adamkimberley]

Someone definitely should have started a slow-clap when he said "tri-vial".

[jojorxy]

what's the meaning of predecessor? wiki says it's the max of the subset {y | y < x}.But what's the definition of '<' in strings?Do I miss something?

[vergigg]

Erik Demaine! Great teacher, I have seen his course MIT 6.046J: Introduction to Algorithms

[manas_singh]

To all the people coming here I would recommend the official papers on McCreight's and Ukonnen's as well.

[georgiansarghi]

16:27 I don't understand the answer to the question. Isn't there a BST for each node?

[raokblee]

It seems to be meant for someone with a degree already in CS/IS. I find reading the lecture notes first is helpful.

[CEngineer]

I would like to know what "vEB" stands for? I've never heard of this data structure before.

[ilyasbambrik]

I dont understand the gain between sorting with triplet and simple double cyclicshifts for the suffix array. Other than that, great course!

[djn]

I don’t like when people refer to anything in an algorithms context, not even a trie (which I would consider a pretty advanced data structure), as “trivial.”

[MeaHeaR]

This is So Amazing, honestly I have absolutely NO idea what shes talking abbout or wear it uséd 😲😲😲

[adityasheth]

Can anyone please explain why is the size of suffix tree O(T)?

[sanskarjaiswal]

Is this course covers aho corasick algorithm

[obinnaubah]

1:30 Doesn't ASCII have only 127 characters?

[dukedex]

My IQ is too low for this. I'm studying ecology, which is about a thousand times easier.

[utkarshshukla]

too much complicated, is there any book source ?

[facitenonvictimarum]

Really a primitive way to teach something so complicated: copying notes to a blackboard. Especially when you consider how much money those students are paying.

[jonsnow]

This is cool and all but this is no use