chapter11
复制本地路径 | 在线编辑
1. 串匹配一般问题
1.1 说明为什么不可以用随机组成来进行性能评估
1.2 说明KMP和BM分别的适用场景
2. 串匹配实例构造(PHILADELPHIA)
2.1 KMP: (next,改进next)
2.2 BM: (bc,ss,gs)
3. 串匹配复杂度分析
3.1 说明暴力算法的期望复杂度为O(n)
3.2 说明KMP的复杂度为O(m+n)
3.3 说明构造SS表的复杂度为O(m)
3.4 说明构造GS表的复杂度为O(m)
4. 串匹配实例构造
4.1 分别构造暴力算法，KMP，坏字符，好字符的最坏情况
4.2 分别构造暴力算法，KMP，坏字符，好字符的最好情况
4.3 简述好字符的改进，即Galil规则
5. 判断题
约定: 大字符串(文本串)的索引为i，小字符串(模式串)的索引为j
5.1 在KMP的算法中，i始终等于已经做过的成功对比
5.2 在KMP的算法中，i-j始终等于已经做过的失败对比
6. Karp-Rabin算法
6.1 说明Karp-Rabin算法为什么采用(d+1)进制，而不是d进制
6.2 说明Karp-Rabin算法是如何解决散列冲突的
6.3 说明Karp-Rabin算法是如何进行指纹更新的