原题链接
1 题目
1.1 题目所需求出内容
对于本题，最终要求：求若干组询问的可行性
1.2 题目背景、允许、禁止与限制
背景：给定一个模板字符串和 nnn 个匹配字符串（匹配字符串均为小写字母，模板字符串除符号外同样均为小写字母）
允许：模板字符串有三种符号，分别为字母，?和*
对于每个匹配字符串，检查其是否与模板字符串相等
相等的条件：将模板字符串中的?替换成任意 111 个小写字母，将*替换成任意 [0,∞)[0,\infty)[0,∞) 个小写字母后模板字符串和匹配字符串完全相等
1.3 题目数据范围与猜测
1≤n≤100,字符串长度≤100000⟶O(n∣s∣)1 \le n \le 100,字符串长度 \le 100000 \longrightarrow O(n|s|)1≤n≤100,字符串长度≤100000⟶O(n∣s∣)
通配符的个数不超过10→通配符的个数不超过10 \to通配符的个数不超过10→ 非常重要的点
1.4 一句话概括题意
给定模板字符串和若干询问字符串，检查每个询问字符串能否通过模板字符串中字符的替换得到
2 题目破题推导
2.1 第一步：大拆小，小组大
观察到很重要的点：通配符的个数不超过10通配符的个数不超过10通配符的个数不超过10
考虑按通配符的位置将模板字符串分割成若干段
2.2 第二步：正向思维转逆向思维
正向思维：直接拿模板去匹配询问字符串
逆向思维：用“段”去匹配。定义 dp[i][j]dp[i][j]dp[i][j] 表示“模板的前 iii 段，能否匹配目标字符串的前 jjj 个字符”
2.3 第三步：分情况讨论
对于第 iii 段，有两种情况
* 第 iii 段后面是一个?
因为?只能匹配一个字符，所以转移 dp[i+1][j+第i段区间长度+1]dp[i+1][j+第i段区间长度+1]dp[i+1][j+第i段区间长度+1] 是可行的
* 第 iii 段后面是一个*
因为*可以匹配 [0,∞)[0,\infty)[0,∞) 个字符
那么转移 dp[i+1][j+第i段区间长度]dp[i+1][j+第i段区间长度]dp[i+1][j+第i段区间长度] 可行，此时代表我不使用*匹配字符
同时因为*可“吞”很多字符，因此如果此时 dp[i][j−1]dp[i][j-1]dp[i][j−1] 可行，则 dp[i][j]dp[i][j]dp[i][j] 也可行
2.4 第四步：优化
判断“段”能否匹配某一区间，需要 O(段长度)O(段长度)O(段长度) 的时间，这样会超时，所以用 字符串hash\huge{字符串hash}字符串hash
3 模型匹配
上面已经讲述
dp是可以设置成bool类型的！
4 最终代码（禁止抄袭，仅用于参考）
错误点：
t.push_back('*') 加的哨兵覆盖了模板串原有的最后一个通配符，导致最后一个段的通配符类型判断错误。哨兵应该用 ?，或者不要把哨兵塞进 loc 里参与通配符类型判断
