数据结构-课件(第四章).pptVIP

§4.2 串的存储结构及操作的虚拟实现 §4.2.1 串的顺序存储结构及操作的虚拟实现 按照BF算法：当比较到某个位置，不匹配时，不管比 过的字符串是什么情况，都是进行回溯！那么，有没有可能 在比较过的串中存在部分匹配的信息呢？？ 假设主串为 s=‘ s1s2s3...sn ‘ 模式串为 t=‘ t1t2t3...tm ’ mn 子串‘ sisi+1...sj’ ‘titi+1...tj’ 分别用 s[i..j] 和 t[i..j] 表示 则模式匹配可描述为： 求最小的 i ， 0?i ? n-m ，使得 t[1..m]=s[i+1,...i+m] I、KMP算法的基本思想： §4.2 串的存储结构及操作的虚拟实现 §4.2.1 串的顺序存储结构及操作的虚拟实现 假设在 s 中从 si+1开始匹配，遇到一个不完全的匹配，即得到一个 q (1=qm)，使得： t[1..q]=s[i+1..i+q] 但 t[1..q+1]s[i+1..i+q+1] i+1 i+q i+q+1 1 q q+1 s t i+1 i+q i+q+1 1 q q+1 s t x ? ? ? §4.2 串的存储结构及操作的虚拟实现 §4.2.1 串的顺序存储结构及操作的虚拟实现 如果能确定一个最小的整数 i’?{i+1,i+2,...,i+q} 使得 t[1..k]=s[i’+1...i’+k]，其中 k=i+q-i’ 那么，哪些测试和比较是多余的？？ k i’+1 i’+k §4.2 串的存储结构及操作的虚拟实现 §4.2.1 串的顺序存储结构及操作的虚拟实现 A、由上面可知：对于 任意 l ， ili’ 有 t[1..k]s[l+1..l+k] 从而可以肯定有 t[1..m]s[l+1..l+m] （部分不匹配，整体肯定不匹配！！） 即下一步匹配可以跳到 si’+1 i+1 i+q i+q+1 1 q q+1 s t x ? ? ? k i’+1 i’+k 都不可能作为 匹配的起点！ ili’ §4.2 串的存储结构及操作的虚拟实现 §4.2.1 串的顺序存储结构及操作的虚拟实现 B、由于 t[1..k]=s[i’+1..i’+k] 所以从 i’ 开始的比较 可以从 i’+k+1 开始，即从 t[k+1] 与 s[i’+k+1] 比较 开始。 那么如何求 i’ 呢？？ i+1 i+q i+q+1 1 q q+1 s t x ? ? ? k i’+1 i’+k t[1..k]=s[i’+1..i’+k] §4.2 串的存储结构及操作的虚拟实现 §4.2.1 串的顺序存储结构及操作的虚拟实现 si+1 si+q t1 tq x si+q+1 si’+k+1 tq+1 si’+1 t[1..q]=s[i+1..i+q] t[1..q+1]s[i+1..i+q+1] t[1..k]=s[i’+1..i’+k] k k tk+1 §4.2 串的存储结构及操作的虚拟实现 §4.2.1 串的顺序存储结构及操作的虚拟实现 假设 k=i+q-i’，所以，确定 i’ 就等价与确定 k, 即在{i+1,i+2,...i+q}中找最小的整数 i’使得 t[1..k]=s[i’+1...i’+k] 等价于在 {0,1,2,...,q-1}找最大 的整数 k，使得t[1..k]=s[i’+1...i’+k] ！！ 从分析可知：t[1..k]是 t[1..q]的最长的既是真前缀 又是真后缀的子串（即长度小于q） 所以，求 k 就是求 t[1..q] 中最长的既是真前缀又是 真后缀的子串的长度。 k与主串无关！！ §4.2 串的存储结构及操作的虚拟实现 §4.2.1 串的顺序存储结构及操作的虚拟实现 假设如何求 k 的问题已经解决，即对于每个t[j]都 求出了最长的前缀串长度k,那么就有：与 t[j]匹配 失败时，应继续与 t[k+1]比较， k+1称为t[j]的失败 函数值,记作 next[j]=k+1 。（教材上是设最长前缀 串的长度为k-1,则next[j]=k,一回事！！） 于是，KMP算法如下： II、KMP算法 §4.2 串的存储结构及操作的虚拟实现 §4.2.1 串的顺序存储结构及操作的虚拟实现 时间复杂度 O（m+n） 为什么？ int index_KMP(seqstring s, seqstring t, int