A leaked password
A sign-up form rejects leaked passwords. Instead of the whole list it holds a Bloom filter of m bits with k positions per word. Build the filter from the given list of words, answer the checks and count how many times the filter was wrong.
The positions of a word are computed exactly as in the article:
- h is the 64-bit FNV-1a hash of the word's bytes: start with 14695981039346656037; for each byte b in order, h ← (h xor b) · 1099511628211 mod 2⁶⁴;
- h₁ is the lower 32 bits of h, h₂ the upper 32 bits of h with the lowest bit set to 1;
- the positions are (h₁ + i · h₂) mod m for i = 0, 1, …, k − 1.
Input
First line: m and k (1 ≤ m ≤ 10⁷, 1 ≤ k ≤ 20). Second: the number of words n (1 ≤ n ≤ 50,000). Third: the words, separated by spaces. Fourth: the number of checks q (1 ≤ q ≤ 50,000). Fifth: the words to check. Words consist of Latin letters, digits and symbols without spaces, 1 to 30 characters long.
Output
For each check, maybe if all its bits are on, or no. On the last line, how many maybe answers went to words that were not on the list.
Examples
Example 1
64 3 5 password qwerty dragon letmein monkey 6 dragon sunshine Qwerty 123456 letmein football
maybe no maybe no maybe no 1
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 7 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
First make your positions match the first example: dragon with m = 64, k = 3 gives positions 30, 1, 36. If they do not match, the mistake is in the hash, not in the filter.
2Hint 2
To count false positives you need the truth: was the word on the list or not. What checks that quickly?
3The idea
The filter is an array of m flags. An insert lights k positions, a check sees whether all are lit. To count errors, keep an ordinary set of the words alongside: a maybe for a word outside the set is a false positive. The set is here only to check the filter; a real sign-up form would not have it.
4Walkthrough
Read everything in one call and work with bytes: in Python sys.stdin.buffer.read().split() gives bytes right away, and looping over them goes byte by byte—just what FNV-1a needs. In Go it is handy to scan the words with bufio.Scanner and ScanWords.
Mask the hash to 2⁶⁴ − 1 after every multiplication: in Go, uint64 overflow does it by itself, but Python integers do not overflow, and the mask has to be applied explicitly. Then cut the hash into two halves and get the positions.
Check yourself on the edge case m = 1: the only bit is lit by the very first word, and after that the filter answers maybe to everything. The formula from the article gives 1 − e⁻¹ ≈ 0.63 here, while in fact we are always wrong: the formula is approximate and assumes many bits.
4+Solution
5Complexity
Hashing a word of length L is O(L), the positions O(k). In all O((n + q)(L + k)) time and m bytes of memory (the flags can be packed into bits, but with m ≤ 10⁷ bytes fit too).
6Common mistakes
- No mask in Python. The hash grows to hundreds of bits and the positions drift. The solution passes the first example if lucky and fails the rest.
- The built-in hash(). In Python it is random for strings on every run—answers will change from run to run.
- Forgetting “| 1” on h₂. Then for an even h₂ some positions coincide, and the bits are wrong.
- Slow input. A hundred thousand words read one by one with
input()cost extra seconds.