3 ms·
>One issue with this technique is when the set of characters grow above 64, so you can no longer give each one a unique bit. You can xor arrays of integers.
by at_compile_time 4y ago
>One issue with this technique is when the set of characters grow above 64, so you can no longer give each one a unique bit.
You can xor arrays of integers.
- thomasahle 4y agoRight, but if the universe of possible characters grow much larger than the window size (as it does in many applications), we want a method that only pays in terms of window size, not universe size.
- twic 4y agoSo 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 :-)
- remram 4y agoIn that case, you might still want to use a similar trick as a first pass (like a bloom filter), and go over the window that is potentially unique again with the HashSet. This should still be faster than using the HashSet for all windows. https://en.wikipedia.org/wiki/Bloom_filter https://en.wikipedia.org/wiki/Bloom_filter