P8630 [Lanqiao Cup 2015 National B] Ciphertext Search

Holmes received a document from Planet X, consisting entirely of lowercase letters. His assistant provided another document: a list of many passwords of length $8$. Holmes found that these passwords were shuffled and hidden in the previous document. Please write a program to search, in the first document, for positions where hidden passwords may appear. You must consider all permutations of each password.

The first line contains a string $s$, consisting only of lowercase letters, with length less than $1024 \times 1024$. The next line contains an integer $n$, indicating that there are $n$ lines of passwords below, where $1 \le n \le 1000$. The next $n$ lines each contain a string, all consisting of lowercase letters, each of length $8$.

Output one integer, representing the total number of matches in $s$ of all permutations of the password on each line.

The first password matches $3$ times, and the second password matches $1$ time, for a total of $4$ times. Time limit: 3 seconds, 512 MB. Lanqiao Cup 2015, 6th National Finals. Translated by ChatGPT 5