严蔚敏 数据结构 kmp算法详解.ppt

4 3 2KMP算法KMP算法是D E Knuth J H Morris和V R Pratt共同提出的 简称KMP算法 该算法较BF算法有较大改进 主要是消除了主串指针的回溯 从而使算法效率有了某种程度的提高 所谓真子串是指模式串t存在某个k 0 k j 使得 t0t1 tk tj ktj k 1 tj 成立 例如 t abab 即t0t1 t2t3也就是说 ab 是真子串 真子串就是模式串中隐藏的信息 利用它来提高模式匹配的效率 一般情况 设主串s s0s1 sn 1 模式t t0t1 tm 1 在进行第i趟匹配时 出现以下情况 这时 应有 t0t1 tj 1 si jsi j 1 si 1 4 1 如果在模式t中 t0t1 tj 1 t1t2 tj 4 2 则回溯到si j 1开始与t匹配 必然 失配 理由很简单 由 4 1 式和 4 2 式综合可知 t0t1 tj 1 si j 1si j 2 si 既然如此 回溯到si j 1开始与t匹配可以不做 那么 回溯到si j 2开始与t匹配又怎么样 从上面推理可知 如果 t0t1 tj 2 t2t3 tj 仍然有 t0t1 tj 2 si j 2si j 3 si 这样的比较仍然 失配 依此类推 直到对于某一个值k 使得 t0t1 tk 2 tj k 1tj k 2 tj 1 且 t0t1 tk 1 tj ktj k 1 tj 1 才有 tj ktj k 1 tj 1 si ksi k 1 si 1 t0t1 tk 1 说明下一次可直接比较si和tk 这样 我们可以直接把第i趟比较 失配 时的模式t从当前位置直接右滑j k位 而这里的k即为next j 例如t abab 由于 t0t1 t2t3 这里k 1 j 3 则存在真子串 设s abacabab t abab 第一次匹配过程如下所示 此时不必从i 1 i i j 1 1 j 0重新开始第二次匹配 因t0 t1 s1 t1 必有s1 t0 又因t0 t2 s2 t2 所以必有s2 t0 因此 第二次匹配可直接从i 3 j 1开始 为此 定义next j 函数如下 max k 0 k j 且 t0t1 tk 1 tj ktj k 1 tj 1 当此集合非空时 1当j 0时0其他情况 next j t abab 对应的next数组如下 voidGetNext SqStringt intnext intj k j 0 k 1 next 0 1 while j t len 1 if k 1 t data j t data k k为 1或比较的字符相等时 j k next j k elsek next k 由模式串t求出next值的算法 intKMPIndex SqStrings SqStringt intnext MaxSize i 0 j 0 v GetNext t next while i t len v i t len 返回匹配模式串的首字符下标 elsev 1 返回不匹配标志 returnv KMP算法 设主串s的长度为n 子串t长度为m 在KMP算法中求next数组的时间复杂度为O m 在后面的匹配中因主串s的下标不减即不回溯 比较次数可记为n 所以KMP算法总的时间复杂度为O n m 例如 设目标串s aaabaaaab 模式串t aaaab s的长度为n n 9 t的长度为m m 5 用指针i指示目标串s的当前比较字符位置 用指针j指示模式串t的当前比较字符位置 KMP模式匹配过程如下所示 上述定义的next 在某些情况下尚有缺陷 例如 模式 aaaab 在和主串 aaabaaaab 匹配时 当i 3 j 3时 s data 3 t data 3 由next j 的指示还需进行i 3 j 2 i 3 j 1 i 3 j 0等三次比较 实际上 因为模式中的第1 2 3个字符和第4个字符都相等 因此 不需要再和主串中第4个字符相比较 而可以将模式一次向右滑动4个字符的位置直接进行i 4 j 0时的字符比较 这就是说 若按上述定义得到next j k 而模式中pj pk 则为主串中字符si和pj比较不等时 不需要再和pk进行比较 而直接和pnext k 进行比较 换句话说 此时的next j 应和next k 相同 为此将next j 修正为nextval j 比较t data j 和t data k 若不等 则nextval j next j 若相等nextval j nextval k voidGetNextval SqStringt intnextval intj 0 k 1 nextval 0 1 while j t len if k 1 t data j t data k j k if t data j t data k nextval j k elsenextval j nextval k elsek nextval k 由模式串t求出nextval值 intKMPIndex1 SqStrings SqStringt intnextval