P4045 [JSOI2009] Password

It is well known that passwords play an invaluable role in the field of information. For ordinary login passwords, the only way to crack them is brute force—trying all possible letter combinations one by one—but this is time-consuming and easy to detect. Therefore, before attempting a brute-force attack, one must do a lot of preparation. After gathering intelligence, we have obtained several useful pieces of information of the form: > "I observed that the password contains the string *." For example, for a password of length $10$ and the observed substrings `hello` and `world`, possible passwords are `helloworld` and `worldhello`. For a password of length $6$ and the observed substrings `good` and `day`, a possible password is `gooday`. With such information, the number of attempts can be greatly reduced. Please write a program to compute all possible passwords. The password may contain only lowercase letters in `a-z`.

The input begins with two integers $L, N$, denoting the password length and the number of observed substrings, respectively. Then follow $N$ lines, each containing a string that describes one observed substring.

The first line of the output contains a single integer: the total number of passwords that contain all observed substrings. If this number is less than or equal to $42$, output all possible passwords in lexicographical order, one per line. Otherwise, output only the total count.

Constraints: For $100\%$ of the testdata, $1 \le L \le 25$, $1 \le N \le 10$, each observed substring has length at most $10$, and it is guaranteed that the output is less than $2^{63}$. Translated by ChatGPT 5