P6540 [COCI 2013/2014 #1] SLASTIČAR

You need to compare some serial numbers.

There are $M$ short serial numbers consisting of digits $0$ to $9$, and one long serial number of length $N$. The process of checking whether serial number $A$ contains a serial number $B$ of length $L$ is as follows: - Compare $A$ with $B$ digit by digit from positions $1$ to $L$. Once a mismatch is found, shift the whole search window one position to the right. If they are confirmed equal, stop comparing. - Shifting the search window means moving the search range from $x$ to $y$ to $x+1$ and $y+1$. - If the remaining digits are not enough for comparison, pad the end of the string with `#`. For example, for the string `563232`, padding from position $4$ to $10$ becomes `232####`. - If all windows have been tried and none matches, stop comparing. For each short serial number, output the number of comparisons made before the comparison process stops.

The first line contains a positive integer $N$. The second line contains a long serial number of length $N$. The third line contains a positive integer $M$. The next $M$ lines each contain a short serial number of length at most $10^5$. The total length of all short serial numbers does not exceed $3\times 10^6$.

Output $M$ integers. The $i$-th integer is the number of comparisons needed for the $i$-th short serial number.

#### Constraints - For $20\%$ of the testdata, $1\le N\le 10^3$, $1\le M\le 500$, and the length of every short serial number is at most $10^3$. - For $100\%$ of the testdata, $1\le N\le 10^5$ and $1\le M\le 5\times 10^4$. - For any character $c$ in any serial number, $c\in\{0,1,2,3,4,5,6,7,8,9 \}$. #### Sample Explanation #### Sample 1 Explanation The first serial number: - The robot looks for the first different digit in each window, making a total of $7$ comparisons. The second serial number: - Try the first position, immediately finds a mismatch: $1$ comparison. - Try the second position, finds a mismatch at the fourth digit: $4$ comparisons. - Try the third position, immediately finds a mismatch: $1$ comparison. - Try the fourth position, finds a match: $4$ comparisons. - Total: $10$ comparisons. The third serial number: - Immediately finds a match, total $3$ comparisons. The fourth serial number: - Finds a match at the second position, total $1+3=4$ comparisons. #### Sample 3 Explanation Compare serial number `11` with window `00` in order: $1$ comparison, then `01`: $1$ comparison, and `1#`: $2$ comparisons, for a total of $4$ comparisons. -------- #### Notes **This problem is translated from [COCI2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST #1](https://hsin.hr/coci/archive/2013_2014/contest1_tasks.pdf) _T6 SLASTIČAR_.** Translated by ChatGPT 5