数据结构串的模式匹配本PPT课件.ppt

第四章串的模式匹配算法 1 本讲内容 4 3串的模式匹配算法 1 朴素的模式匹配算法 2 KMP算法 1 模式串的next和nextval函数值2 手工模拟KMP算法的执行过程 采用串的定长顺序存储结构 讨论不依赖于其他串操作的模式匹配算法 子串定位操作 2 朴素的模式匹配算法 Index S T pos 算法思想 从主串S的第pos个字符起和模式T的第一个字符比较 若相等 则继续逐个比较后续字符 否则 从主串的下一个字符起再重新和模式T的字符比较 依次类推 直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等 则称匹配成功 否则称匹配失败 匹配成功时 返回和模式T中第一个字符相等的字符在主串S中的位置 匹配失败时 返回零 3 朴素的模式匹配算法 S串 pos i T串 j i j i j i j i j T串 4 朴素的模式匹配 主串S ababcabcacbab 模式串T abcac pos 1 i 3第一趟匹配 ababcabcacbababc j 3 i 2第二趟匹配 ababcabcacbaba j 1 i 7第三趟匹配 ababcabcacbababcac j 5 5 第四趟匹配 ababcabcacbaba j 1 i 5第五趟匹配 ababcabcacbaba j 1 i 11第六趟匹配 ababcabcacbababcac 成功 j 6 i 4 6 intIndex SStringS SStringT intpos 返回子串T在主串S中第pos个字符之后的位置 若不存在 则函数值为0 其中 T非空 1 pos StrLength S i pos j 1 while iT 0 returni T 0 elsereturn0 Index i j 2 7 算法分析 2 算法最坏情况下的时间复杂度为O n m 1 如果主串中可能存在多个和模式串 部分匹配 的子串 因而引起主串中指针i的多次回溯 8 上面的模式匹配只需三趟 主串S ababcabcacbab 模式串T abcac i 3第一趟匹配 ababcabcacbababc j 3 next 3 1 i 3第二趟匹配 ababcabcacbababcac j 5 next 5 2 i 7第三趟匹配 ababcabcacbab a bcac j 2怎么得来的呢 这就是KMP算法 9 KMP算法 KMP Knuth Morris Pratt三人发明 特点 无需回溯 在O n m 的时间量级上完成串的模式匹配操作 10 2020 2 6 11 KMP算法 假设主串S为 s1s2s3 sn 模式串T为 p1p2 pm 若si与pj发生失配 则有 si j 1 si 1 p1 pj 1 1 由 1 若k j 则有 si k 1 si 1 pj k 1 pj 1 3 若主串不回溯 设此时将与模式串中第k k j 个字符继续比较 则有 si k 1 si 1 p1 pk 1 2 由 2 和 3 则下式成立 p1 pk 1 pj k 1 pj 1 4 该等式只与模式串有关 与主串无关 12 KMP算法 模式串的next函数定义 若模式串P为 abaabc 由定义可得next函数值 13 i 2第一趟匹配 主串acabaabaabcacaabc模式串ab j 2next 2 1 i 2第二趟匹配 主串acabaabaabcacaabc模式串a j 1next 1 0 i 3 i 8第三趟匹配 主串acabaabaabcacaabc模式串abaabc j 1 j 6next 6 3 i 8 i 12第四趟匹配 主串acabaabaabcacaabc模式串 ab aabc j 3 j 7 KMP算法手工模拟 主串S acabaabaabcacaabc 模式串T abaabc 14 intIndex KMP SStringS SStringT intpos 1 pos StrLength S i pos j 1 while iT 0 returni T 0 匹配成功elsereturn0 Index KMP 15 不存在这样的k 则next j 1 1 求next函数值的过程是一个递推过程 分析如下 已知 next 1 0 假设 next j k 则 next j 1 k 1 若 T j T k 则需往前回溯 检查T j T 又T j T k k next j 即 next j 1 next j 1 k 即 next j 1 next k 1 16 01122343 求模式串的next函数值举例 这实际上也是一个匹配的过程 不同在于 主串和模式串是同一个串 17 voidget next SString get next 18 next函数的改进 当i 4 j 4时si pj 由next j 的指示还需进行i 4 j 3 i 4 j 2 i 4 j 1等三次比较 实际上 由于模式中第1 2 3个字符和第4个字符都相等 因此这种比较是不必要的 可以将模式串一次向右滑动4个字符直接进行i 5 j 1的比较 也就是说 若next j k 当si与pj失配且p