3 ms·
Another possible detail this misses - I learnt about De Bruijn sequences from Samy Kamkar here: http://samy.pl/opensesame/ http://samy.pl/opensesame/ (scroll
by bigiain 9y ago
Another possible detail this misses - I learnt about De Bruijn sequences from Samy Kamkar here:
http://samy.pl/opensesame/ http://samy.pl/opensesame/
(scroll about 1/3rd way down to the "(U) The OpenSesame Attack" section for the bits relevant to this discussion...)
You don't need to enumerate every n-bit sequence, you just need to enumerate a (shorter - by 62% in Samy's 12 bit case) sequence that contains all the n-bit sequences.
- saagarjha 9y agoInterestingly, there was an old USAMTS problem that had De Bruijn sequences in it, though I wasn't aware of it at the time: http://www.usamts.org/Tests/Problems_25_1.pdf http://www.usamts.org/Tests/Problems_25_1.pdf
- gumby 9y agoThis is the heart of the Boyer-Moore string searching algorithm too.