P2536 [AHOI2005] Virus Detection

The exploration on Planet Samuel continues. Very fortunately, near the south pole of Planet Samuel, the exploration robot discovered a huge ice lake! The robot collected many DNA fragments from this ice lake and sent them back to the research base. After several days and nights of research, scientists found that many of these DNA fragments belong to unknown viruses! Each DNA fragment is a sequence composed of `A`, `C`, `T`, and `G`. Scientists also summarized the "virus template fragment" on Planet Samuel. A template fragment is represented by a sequence of `A`, `C`, `T`, `G` plus wildcards `*` and `?`. Here, `*` means it can match $0$ or any number of characters, and `?` means it can match any single letter. If a DNA fragment can match the "virus template fragment", then that DNA fragment is an unknown virus. For example, suppose the "virus template fragment" is `A*G?C`. The DNA fragments `AGTC` and `AGTGTC` are viruses, while the DNA fragment `AGTGC` is not a virus. Since the non-virus parts among the DNA fragments collected by the robot are of very high research value, scientists want to identify which DNA fragments are not viruses and send those non-virus DNA fragments back to the space station for further research. This task is assigned to Xiaolian (pinyin: Xiaolian). Please write a program to count which DNA fragments are not viruses.

There are $N+2$ lines of input. The first line contains a string composed of `A`, `C`, `T`, `G`, `*`, and `?`, representing the "virus template fragment". The length of the "virus template fragment" does not exceed $1000$. The second line contains an integer $N$, representing the number of DNA fragments collected by the robot. Each of the following $N$ lines contains a string composed of `A`, `C`, `T`, and `G`, representing a DNA fragment.

Output a single line with an integer $M$, which is the number of DNA fragments that are not viruses.

The DNA fragment `AGTGC` in the input is not a virus. For all testdata, $0 < N < 500$. In particular: - The length of each DNA fragment does not exceed $500$. - The lengths of the "virus template fragment" and each DNA fragment are at least $1$. Translated by ChatGPT 5