CS
Problems Base course RU

Problem

Similar passwords

similarity deduplication security precomputation hash table

A service does not want to allow passwords similar to leaked ones: if password is forbidden, password1 is no better. To understand how full of variations the leak lists are, the pairs of similar passwords in them have to be counted.

The similarity of passwords is measured by trigrams, substrings of three consecutive characters. The trigram set of a password is all its substrings of length 3, each once. The similarity of two passwords is the Jaccard coefficient of their sets: |A ∩ B| / |A ∪ B|. Count how many pairs of passwords in the list have similarity at least T/100. The tests include the 10,000 most common passwords from the open SecLists list.

Input

The first line holds the number of passwords n and the threshold T (1 ≤ n ≤ 4·104, 50 ≤ T ≤ 100). Then n distinct passwords, one per line: 4 to 30 printable ASCII characters without spaces.

Output

One number: how many unordered pairs of passwords have similarity at least T/100.

In the second example abab, baba and ababab are different passwords with the same trigram set {aba, bab}, and aaaa and aaaaaa have the set {aaa}: four pairs of similarity 1.

Examples

Example 1

Input
7 60
password
password1
passw0rd
drowssap
123456
1234567
qwerty
Output
2

Example 2

Input
5 50
abab
baba
ababab
aaaa
aaaaaa
Output
4

Limits

Time · Python
8000 ms
Time · Go
1500 ms
Memory
256 MB
Judging
6 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

If a password of five trigrams has similarity at least 0.6 with another, how many trigrams do they have in common at least? And can it be that among the first three trigrams of a password, in any order fixed in advance, there is no common one?

2Hint 2

Choose an order in which the rarest trigrams come first. Then the lists “which passwords have this trigram among their first” will be short.

3The idea

If J(A, B) ≥ t, then |A ∩ B| ≥ t·|A ∪ B| ≥ t·|A|, that is, there are at least ⌈t·|A|⌉ common elements. Write all the sets in one common order. Then among the first |A| − ⌈t·|A|⌉ + 1 elements of A there is a common one: otherwise all the common ones would fit into the last ⌈t·|A|⌉ − 1 places. The earliest common element lies in these “prefixes” of both A and B. So the candidates are only the pairs whose prefixes intersect, and an inverted index over the prefixes gives them. This is the prefix filter from the article.

4Walkthrough

Count in how many passwords each trigram occurs, and order the trigrams from rare to frequent. Process the passwords in increasing number of trigrams: then every partner already processed has a set no larger. For the next password s go through its prefix; via the index find the passwords that have the same trigram in their prefix, and check each one once. First the size filter: J ≤ |o| / |s|, and if |o| < t·|s|, the pair can be skipped. Then the exact intersection. After that put the prefix of s into the index. All comparison is in integers: 100·|A ∩ B| ≥ T·|A ∪ B|, without division.

On 10,000 passwords with a threshold of 0.6 there are 50,005,000 pairs and 62,762 exact checks, eight hundred times fewer. There are 4484 similar pairs: password and password1, 123456 and 1234567. On 35,516 passwords made of words of War and Peace with a threshold of 0.7: 574,019 checks instead of 630 million pairs.

4+Solution
5Complexity

Counting and sorting the trigrams is O(L + G log G), where L is the total length of the passwords and G the number of distinct trigrams. After that, the sum of the lengths of the index lists scanned plus the exact checks of candidates. In the worst case, when all passwords consist of the same frequent trigrams, this is O(n²) again, but on real lists there are hundreds of times fewer candidates than pairs.

6Common mistakes
  • All pairs. The answer is correct, but 5·107 pairs is already a lot for Python, and 6·108 for any language.
  • Trigrams as a list. Repeats count once: ababab has two trigrams, not four.
  • Comparing in fractions. A similarity exactly equal to the threshold must count; floating-point division may lose it.
  • A prefix of the wrong length. |A| − ⌈t·|A|⌉ + 1 elements are needed; one fewer, and pairs whose common element is the last in the prefix are lost.
  • Frequent trigrams first. The answer is the same, but prefixes will hold 123 and ass with long lists: on the passwords from the novel there will be 18 million checks instead of 574 thousand, thirty times more.

Algorithms behind it

SYS Algorithm MinHash and LSH A signature of K hash minima: the share that match estimates Jaccard similarity; LSH bands bring similar pairs into the same buckets. O(K·S) for the signatures, O(n·b) for the buckets, plus checking candidates 2 problems SYS Data structure Inverted index and BM25 A dictionary “word → documents that contain it”: a query reads a few short lists instead of all the texts. O(total length of the query words' lists); AND by galloping O(m·log(n/m)) 2 problems
The algorithms catalogue