2 ms·
The Suffix Array is surprisingly cool and useful https://en.wikipedia.org/wiki/Suffix_array https://en.wikipedia.org/wiki/Suffix_array The Alias Table for sa
by dahart 4y ago
The Suffix Array is surprisingly cool and useful https://en.wikipedia.org/wiki/Suffix_array https://en.wikipedia.org/wiki/Suffix_array
The Alias Table for sampling a discrete distribution in O(1) time is a very clever idea https://www.keithschwarz.com/darts-dice-coins/ https://www.keithschwarz.com/darts-dice-coins/
- dinobones 4y agoThe fact that suffix trees/suffix arrays can be built in O(n) is IMO the most surprising and "magical" result in computer science. To me, more surprising than median of medians/quick select. There might be more "magical"/surprising things that are obscure and I am unaware of, but to me, this is it. :)
- adgjlsfhk1 4y agowhat about randomized O(n) minimum spanning trees?