2 ms·
So you use a sparse bitmap, ie a hash set. The size of the hash set is bounded to the size of the window, so this should be pretty efficient. If you have a hug
by twic 4y ago
So you use a sparse bitmap, ie a hash set. The size of the hash set is bounded to the size of the window, so this should be pretty efficient.
If you have a huge string, a huge alphabet, and also a huge window, then probabilistic techniques start to make sense. But let's not run while we can successfully walk!
- thomasahle 4y agoSure. We can always use a hash set, but then you need to use chaining or some other collision resolution policy. The whole of this whole exercise is to avoid that and get something really fast and truly constant time :-)