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

你需要比较一些序列号。

现有 $M$ 个由数字 $0$ 到 $9$ 组成的短序列号和一个长度为 $N$ 的长序列号。 检查序列号 $A$ 是否包含长度为 $L$ 的序列号 $B$ 的过程如下： - 将 $A$ 从位置 $1$ 到 $L$ 逐位与 $B$ 比较，一找到不同就将搜索段整体向后移，如果确定相等则停止比较。 - 将搜索段后移意为把 $x$ 到 $y$ 的搜索区域后移为 $x+1$ 和 $y+1$。 - 若剩下用于比较的位数不够，则在字符串末尾填充 `#`。如字符串为 `563232`，从位置 $4$ 到 $10$ 的填充为 `232####`。 - 若尝试了所有段均不匹配则停止比较。 对于每个短序列号，输出停止比较前比较的次数。

输入的第一行是正整数 $N$。 输入的第二行是一个长度为 $N$ 的长序列号。 输入的第三行包含正整数 $M$。 接下来 $M$ 行每行包含一个长度不超过 $10^5$ 的短序列号。 短序列号总长度不超过 $3\times 10^6$。

输出 $M$ 个整数，即对于第 $i$ 个短序列号所需的比较次数。

#### 【数据规模与约定】 - 对于 $20\%$ 的数据，$1\le N\le 10^3$，$1\le M\le 500$，任意短序列号长度均不超过 $10^3$。 - 对于 $100\%$ 的数据，满足 $1\le N\le 10^5$，$1\le M\le 5\times 10^4$。 - 对于任意序列号中的一位字符 $c$，满足 $c\in\{0,1,2,3,4,5,6,7,8,9 \}$。 #### 【样例解释】 #### 样例 1 解释 第一个序列号： - 机器人为每个段查找不同的第一位数字，总共进行 $7$ 次比较。 第二个序列号： - 尝试第一个位置，立即发现差异，$1$ 次比较。 - 尝试第二个位置，找到第四个数字的差异，$4$ 次比较。 - 尝试第三个位置，立即找到差异，$1$ 次比较。 - 尝试第四个位置，找到匹配，$4$个比较。 - 总计 $10$ 次比较。 第三序列号： - 立即找到匹配项，总计 $3$ 个比较。 第四个序列号： - 在第二个位置找到匹配项，总计 $1+3=4$ 个比较。 #### 样例 3 解释 按顺序将序列号 `11` 与段 `00`，$1$ 次比较，`01`，$1$ 次比较，和`1#`，$2$ 次比较，总计 $4$ 次比较。 -------- #### 【说明】 **题目译自 [COCI2013-2014](https://hsin.hr/coci/archive/2013_2014/) [CONTEST #1](https://hsin.hr/coci/archive/2013_2014/contest1_tasks.pdf) _T6 SLASTIČAR_。**