3798. [JZOI 2022 day1]chi-a↗na→go~~

【题目描述】

千束太可爱了，于是她给你一个由字符 "$1$" 到 "$9$" 组成的字符串 $s$。她给你若干次询问，每次询问一个长度为 $10$ 的字符串 $t$ 在 $s$ 中出现了多少次。

但是千束不拘小节，她指定了 $t$ 中的一些位置，用 "$?$" 表示。这些位置可以匹配任意单个字符。

保证每个 $t$ 中 "$?$" 不超过 $4$ 个。

【输入格式】

第一行两个整数 $n,q$ ，表示 $s$ 的长度和询问次数。

第二行一个由字符 "$1$" 到 "$9$" 组成的字符串 $s$。

接下来 $q$ 行，每行一个长度为 $10$ 的字符串 $t$， 限制如题所示。

【输出格式】

一共 $q$ 行，表示每次询问的答案。

【样例1输入】

19 3
1234123912341234123
123?123?12
1234123?12
1239123?12

【样例1输出】

3
2
1

【样例2输入输出】

点击下载样例2 

【数据规模与约定】

对于其中 $20\%$ 的数据，$n,q\ \leq 100$。

对于其中 $40\%$ 的数据，$n\ \leq 10000,q\ \leq 50000$。

对于其中 $60\%$ 的数据，$n\ \leq 50000,q\ \leq 50000$。

对于另外 $20\%$ 的数据，$n\ \leq 50000,q\ \leq 50000$，所有给出字符串只包含 "$1$"," $2$", "$?$"。

对于 $100\%$ 的数据，$n,q\ \leq\ 2e5$。

【来源】

焦作一中 NOIP 2022 模拟赛2022.11.22 pro2