5 ms·
This article’s technique can definitely expand into dynamically allocated bitsets.
by nynx 4y ago
This article’s technique can definitely expand into dynamically allocated bitsets.
- thomasahle 4y agoSay we don't want to allocate memory dynamically though. We just want to allocate O(W) bits at the start of the program. Can you still do it?
- FartyMcFarter 4y agoIn that case the complexity becomes O(N * A) where A is the size of the alphabet, since at every step you have to go through the whole bitset in order to count how many bits are set. Edit - actually it should be possible to update the count incrementally, so it should still be O(N) I think.