Problem G
Dictionary Attack
In choosing a password, it’s important to avoid dictionary words or simple variants of them. Using a password based on a dictionary word makes it easier for an attacker to break into your account by simply guessing dictionary words and similar strings.
We say that a password is unacceptable if it can be obtained by making three or fewer elementary changes to a dictionary word. An elementary change can be either of the following.
-
Replace any one character with a decimal digit.
-
Transpose any two adjacent characters.
Input
Input begins with a positive integer $N \leq 1\, 000$ and a list of $N$ dictionary words, one per line. After this list is a sequence of up to $250$ password candidates, one per line up to the end of file. The list of dictionary words use only uppercase and lowercase letters (a–z), and the password candidates use only uppercase and lowercase letters (a–z) and decimal digits $0$–$9$. Each dictionary word and password candidate is at most $15$ characters long.
Output
From the list of password candidates, print out a list of just the acceptable passwords in the same order, one per line.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 book apple secret December vertigo book b00k alppe a1ppe secret esrcte erscte vreitg0 arithmetic D3c3m63r d3c3mb3r ap1p3 |
erscte arithmetic D3c3m63r d3c3mb3r |
