16. Strings

[@ScipioWasHere]

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

[@mayiwang]

41:09 suffix trees

[@casino-daddy]

thanks

[@ShafaetAshraf]

Just adding this for those who got confused like me at 16:42. en.wikipedia.org/wiki/Ternary_search_tree The BST representation of trie is referring to this.

[@zuhrymousa12345]

Erik is bae

[@videofountain]

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

[@王宇翔-s3t]

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

[@dragon_warrior_]

6.006* 6.046 is advance

[@devangsrivastava6736]

OH I WAS SOOOOOO LOOKING FOR THISSSS

[@adamkimberley2575]

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

[@manas_singh]

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

[@raokblee2157]

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

[@illiachalyk195]

On the site, it says that it is for graduate level, so I guess you're right

[@TomerBenDavid]

computer science rules

[@NitishRaj]

kzbin.info/www/bejne/oaawpnmrbq6Fqtk subscribe for more computer science lectures

[@georgiansarghi5608]

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

[@imprsnt]

No, Each Trie Node is broken down into a BST.

[@xinli6243]

I think you are correct, each node is a "tiny" BST, What confuses me was he said the space is O(T), I think it should be O(T*log(Sigma))

[@xinli6243]

sorry, I just realized it is O(T). If your are a java user, BST means each node has a TreeMap object in it.

[@jojorxy3977]

what's the meaning of predecessor? wiki says it's the max of the subset {y | y < x}.But what's the definition of '

[@rishabhghosh155]

compare lexicographic ordering (ie a < c), instead of comparing magnitudes (ie with numbers 4 < 6)

[@NaderHGhanbari]

In simpler terms, dictionary order. In other words: If you were to create a dictionary, would you put x before y or y before x?

[@ilyasbambrik1765]

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

[@petertweh5587]

2111e3eee71w60

[@nXqd]

Thanks for the great video :)

[@dhruvjoshi8744]

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.

[@TERRY04104]

Here is what I think how the example in the lecture works: say T = "banana" and we would like find all occurrences of T[1:4] which is "ana", the constant time query would be: 1. find the leave node representing T[1:]; 2. Going upward through the links from that leave node for 4 -1 = 3 characters; 3. We reach the last(highest) node through the ancestor links, then all the occurrences of T[1:4] would be all the leave nodes that are descendants of this node, in this case T[1:] and T[3:].

[@facitenonvictimarum]

Come, mister tally man, tally me banana Daylight come and me wan' go home

[@djn138]

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.”

[@sanskarjaiswal8239]

Is this course covers aho corasick algorithm

[@siobhanahbois]

No, I just watched the whole thing and was disappointed, for some reason this video showed up in search results when searching for 'aho corasick'.

[@MeaHeaR]

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

[@obinnaubah9045]

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

[@djn138]

128, yes en.m.wikipedia.org/wiki/ASCII

[@darkworld9399]

@@djn138 extended Ascii have 256 characters..

[@CEngineer2010]

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

[@lucacavalleri8649]

van Emde Boas (trees) en.wikipedia.org/wiki/Van_Emde_Boas_tree

[@saikumark6327]

kzbin.info/www/bejne/np61ln15qtWVhLc

[@dukedex5043]

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

[@adityasheth]

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

[@alanhasan2898]

because there are |T| suffixes which gives you |T| nodes. You actually don't store the suffix string on each edge, you store an interval with the first and last character that it matches. This requires, however, that you keep the original string for reference.

[@alanhasan2898]

or a more simple answer, it's a compact trie.

[@samiadel7043]

❤️💜❤️

[@utkarshshukla5252]

too much complicated, is there any book source ?

[@mitocw]

There is no book for the course but there are a number of notes from the instructor and from a student. See the "Calendar and Notes" section of the course on MIT OpenCourseWare for the materials at: ocw.mit.edu/6-851S12. Best wishes on your studies!

[@jonsnow1996]

This is cool and all but this is no use

[@davidjames1684]

roughly 4 min elapsed, we want order T space. Why? Who cares about space in this day and age of gigabytes? Many times the more wasteful you are with storage, the quicker you can manipulate data. For example, a sparse hash table vs. a tightly packed one with collision resolution.

[@stanislavnikolov7423]

woooosh

[@adityasheth]

Consider a text with 10^10 letters. Do u have space to store O(T^2) space now?

[@aronsarmasi2368]

I regularly work with data on the order of 10+ TB, and so yeah, I care about space.

[@rraviravir]

many times is not always - if u can trade in a bit more space and get cpu, then u have a useful algo - or else just taking more space is wasteful if there is no payoff - so space complexity is important too

[@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.

[@sharjeeltahir5583]

shit lectures, dont know why people are voting so high. Maybe its because of the brand

[@dilipkumar2k6]

Agreed :-)

[@karthikk5895]

Please don't pollute the learning atmosphere. You can share your opinion when you're intellect matches professors'.