KMP算法ppt课件.ppt

1 第四章字符串模式匹配算法 什么是模式匹配 在一般的编辑软件中 经常要遇到在一个给定的文本中查找一个特定的字符串的问题 这就是字符串匹配 也称模式匹配 设P是一个模式字符串 简称模式 其长度为m s是一个正文字符串 简称正文 其长度为n 通常认为n m 2 简单算法 Brute Force算法 算法描述 从正文s和模式p的第一个字符出发 将s和p的字符依次逐个进行比较 如果p中的所有字符均与s中的对应字符匹配 则说明匹配成功 如果在比较过程中发现了一个字符不匹配 则将模式p沿正文s向后移动一个字符的位置 然后再从p的第一个字符开始与中的对应字符逐个进行比较 以此类推 直到匹配成功或到达的末段为止 3 2 Brute Force算法的实现 intString FindSubstr constString 4 模式匹配的KMP算法 基本思想 当模式p与正文s进行比较的过程中发现不匹配时 找到一种模式p沿正文s向后移动的规则 以便使得正文s中失去匹配的字符以前的字符不再参与比较 即只从当前失去匹配的字符开始与模式p中的字符继续依次进行比较 并且又不错过模式被发现的机会 示例 5 算法分析 假设正文为 s0s1 sn 1 模式为 p0p1 pm 1 要实现改进算法 也就是要解决下述问题 当匹配过程中产生失配时 即si pj 模式 向右滑动 可行的距离有多远 换句话说 当正文中第i个字符与模式中第j个字符 失配 时 正文中第i个字符应与模式中哪个字符相比较 6 假设此时应与模式中第k个字符继续比较 其中k应具有以下两个性质 1 k j 因为当失配时必然使模式p向后移 从而导致k j 移的幅度越小 k与j相差越小 2 k应取所有可能值中的最大值 因为取最大值就意味着移的幅度最小 也就避免错过成功匹配的机会 根据这个假设 必然使得下式成立 p0p1 pk 1 si ksi k 1 si 1 1 而已经得到的 部分匹配 的结果是 pj kpj k 1 pj 1 si ksi k 1 si 1 2 7 2 式的由来是 当初正文中的第i个字符与模式中的第j个字符失配时 说明两者之前的j个字符肯定是一样的 而k j 所以前k个字符也是相同的 这就得出 2 式 由 1 2 两式便可得 p0p1 pk 1 pj kpj k 1 pj 1 3 3 式的结论可如下描述 在模式p中 前k个字符与第j个字符之前的k个字符相同 8 设next j 表示 当模式中第j个字符与正文中相应字符 失配 时 在模式中重新和正文中该字符进行比较的字符的位置 并令next j k Next数组的完整定义如下 9 Next 0 1表示当模式p的第0个字符失去匹配时应将p沿正文方向右移一个位置 也即使p的第一个字符与正文s的下一个字符进行比较 利用next数组进行模式匹配示例 10 如何预先求得next数组值 首先要明确一点 next数组的求值只与模式p有关 而与具体的正文s无关 我们可用递推的方法求next数组值 假设已求得next j k 根据定义可得 p0p2 pk 1 pj kpj k 1 pj 1 那么next j 1 11 1 若pk pj 则表明 p0p1 pk pj kpj k 1 pj 并且不可能存在k k满足上式 那么next j 1 k 1式1也就是 next j 1 next j 12 若pk pj 则表明 p0p1 pk pj kpj k 1 pj 这时如何求next j 1 呢 有两种可能情况 12 转化法 式1的结论可这样描述 何时的k使得pk pj 就用此时的k代入式1 而现在的k是pk pj 因此必须要换成另外一个 k 并设它为k2 以使得pk2 pj 问题又出来了 k2如何得来 如图 要使得k转为k2 实际上就是将p往右移 移动后p 的j对应p的k2 13 k2 到底是多少首先取决于另一个前提条件 p0p1 pk2 1 pj k2pj k2 1 pj 1 如图 实际上 k2 next k 14 那么 满足了这个前提条件 是否就满足pk2 pj了呢 显然两者互不相干 也就是说 仅移动一次不一定满足pk2 pj 如果移动一次后得到k2仍然不满足pk2 pj 就要按照前提条件再移动一次 依次类推 直到pkn pj 或kn 0为止 此时有 next j 1 kn 1而kn next kn 1 k1 k next j 15 由于 kn kn 1