P2030 Remote-Controlled Cars

Pingping takes Yunyun to an amusement park and sees $n$ beautiful remote-controlled cars. Each car has a unique name name[i]. Yunyun has long wanted to play the car whose name is $s$. However, since Yunyun is still young, the name she imagines might be a prefix of some car’s name (that is, there exists an $i$ such that $s$ is a prefix of name[i]); in this case, she can play the $i$-th car. Or it might be a completely made-up name that is not a prefix of any car’s name; in that case, she cannot play anything. You need to complete the following tasks: 1. Yunyun thinks of $m$ desired names. Tell her how many times she can play. 2. Due to the staff’s careless operation, each car’s placement may have a slight error: the original $i$-th car may now be at any one of the positions $i-1$, $i$, or $i+1$ (the position of the $1$-st car cannot be $0$, and the position of the $n$-th car cannot be $n+1$). Calculate how many possible permutations there are. Note: The testdata guarantees that when $s$ is a prefix of name[i], the index $i$ is uniquely determined. A car can be played multiple times.

The first line contains two positive integers $n$ and $m$. The next $n$ lines each contain one string name[i], the name of the $i$-th car. Then the next $m$ lines each contain one string $s$, the name Yunyun wants.

Output two lines: - The first line contains the number of times Yunyun can play. - The second line contains the number of possible permutations.

Note: - All strings are strictly case-sensitive and have length less than $255$. Constraints: - For $20\%$ of the testdata, $n \le 10$, $m \le 10$. - For $40\%$ of the testdata, $n \le 1000$, $m \le 1000$. - For $100\%$ of the testdata, $n \le 10000$, $m \le 10000$. Translated by ChatGPT 5