P6749: 字符串匹配
传统题
4.000s
时间限制
512MB
内存限制
4 提交
1 解决
【题目描述】
【题目描述】
千束太可爱了，于是她给你一个由字符"1"到"9"组成的字符串 。她给你若干次询问，每次询问一个长度为10的字符串 t 在 s 中出现了多少次。
但是千束不拘小节，她指定了 t 中的一些位置，用"?"表示。这些位置可以匹配任意单个字符。
保证每个 t 中"?"不超过4个。
【输入格式】
第一行两个整数 n,q，表示 s 的长度和询问次数。
第二行一个由字符"1"到"9"组成的字符串 s。
接下来 q 行，每行一个长度为10的字符串 t， 限制如题所示。
输出格式
一共 q 行，表示每次询问的答案。
【样例】
input1
19 3
1234123912341234123
123?123?12
1234123?12
1239123?12
output1
3
2
1
【数据范围】
对于20%的数据，n,q<=100。
对于40%的数据，n<=10000,q<=50000。
对于60%的数据，n<=50000,q<=50000。
对于另外20%的数据，n<=50000,q<=50000，所有给出字符串只包含"1","2","?"。
对于100%的数据，n,q<=2e5。