原题链接
1 题目
1.1 题目所需求出内容
对于本题，最终要求：一个具体值
1.2 题目背景、允许、禁止与限制
背景：有一个只含有a c t g ? * 的病毒模板序列和 nnn 个DNA片段
允许：
* 一个 ? 可以代表任意一个 a c t g
* 一个 * 可以代表任意 sss 个 a c t g 注：s∈[0,∞)注：s \in [0,\infty)注：s∈[0,∞)
求有多少个DNA片段 不和 原病毒模板序列 相等（这里的相等并不一定是完全相等，可以是通过 ? 和 *的代替变化而成相等）
禁止：
限制：
1.3 题目数据范围与猜测
1≤n≤500⟶O(n3)1 \le n \le 500 \longrightarrow O(n^3)1≤n≤500⟶O(n3)
1.4 一句话概括题意
有一个病毒模板序列和若干个DNA片段，求有多少个DNA片段 不和 原病毒模板序列 相等
2 题目破题推导
2.1 正向思维转逆向思维
问有多少个DNA片段 不和 原病毒模板序列 相等，那我们可以求有多少个DNA片段 和 原病毒模板序列 相等，再用总数减去这个值
2.2 以终为始（化繁为简）
2.2.1 没有 ? 和 * 的情况
可以直接用病毒序列检查每个DNA片段，看是否相等
2.2.2 有 ? 没有 * 的情况
* 如果不是 ?
那还是和 2.2.1 一样
* 如果是 ?
因为 ? 必须代表 111 个字母，因此相当于检查每个DNA片段当前这一项能往 [a,c,t,g][a,c,t,g][a,c,t,g] 哪块走
2.2.3 有 ? 也有 * 的情况
* 如果是字母
和 2.2.1 一样
* 如果是 ?
和 2.2.2 一样
* 如果是 *
分三种可能：
一种是跳过 *，匹配下一个字符
一种是把 * 看成一个 ?
一种是把 * 看成一个 ? 加一个 *
3 模型匹配
> 格式为："关键词：...... ⟶\longrightarrow⟶ ......\huge{......}......"
关键词：字符串匹配算法 ⟶\longrightarrow⟶ 字典树\huge{字典树}字典树
关键词：匹配过程往下深入 ⟶\longrightarrow⟶ dfs\huge{dfs}dfs
但是，因为 * 的递归调用太多，因此需要剪枝
记录一个 size 数组记录 sizeisize_isizei 代表以 iii 为根节点的字典树子树含有多少没匹配的点，不断更新，直到子树中所有都匹配完毕，则直接停止
4 最终代码（禁止抄袭，仅用于参考）
