P3735 [HAOI2017] String

Given a string $ s $ and $ n $ strings $ p_i $, for each string $ p_i $ count the number of its occurrences in $ s $. Note that the definition of equality between two strings is slightly modified here. Given a constant $ k $, for two strings $ a, b $, we define $ a = b $ if the following hold: 1. $ |a| = |b| $. 2. For all $ a_i \ne b_i $ and $ a_j \ne b_j $, it holds that $ |i - j| < k $. If $ |a| = |b| \le k $, then we regard $ a = b $.

The first line contains an integer $ k $. The second line contains a string $ s $. The third line contains an integer $ n $, followed by $ n $ lines, each containing a string denoting $ p_i $. All characters have ASCII codes in the range $ 33 $ to $ 126 $.

Output $ n $ lines, where the $ i $-th line is the number of occurrences of $ p_i $ in $ s $.

For $ p_1 $, $ xz = xy, xz = yz $, because there is only one differing position. For $ p_2 $, $ y = x, y = y, y = z $, similarly. For $ p_3 $, $ xzy \ne xyz $, the maximum difference $ = 1 $ does not satisfy $ < k = 1 $. Constraints - For $ 20\% $ of the testdata, it holds that: $ |s|, \Sigma |p_i| \le 10^3 $. - For another $ 20\% $ of the testdata, it holds that: $ n \le 100 $. - For another $ 20\% $ of the testdata, it holds that: $ |s|, \Sigma |p_i| \le 5 \cdot 10^4 $. - For $ 100\% $ of the testdata, it holds that: $ |s|, \Sigma |p_i| \le 2 \cdot 10^5 $. Translated by ChatGPT 5