个模式的next(j) j:123456789 ■模式: a b aa b aaa b next]:011223452 依次以此类推可得其余元素的next(j)。 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 11 一个模式的next(j) ◼ j ： 1 2 3 4 5 6 7 8 9 ◼ 模式 ： a b a a b a a a b ◼ next[j] ： 初始化：next[1] = 0。 0 没有相应的k，next(j)为1。 1 1 k = 2，下次从第二个元素开始比较。 2 2 依次以此类推可得其余元素的next(j)。 3 4 5 2
滑动不会造成遗漏 ■KMP算法不再是将正文依次和模式中的 元素逐个地进行匹配,而是当出现“失 配”时从模式的第k(k=next〔j)个元素开 始重新比较,这样会不会遗漏掉可以匹 配的子串呢? ■不会的。因为滑动的距离next(j)被定义为 满足p1,P=pk+1…p1的最大的k。 2021/22 计算机算法设计与分析 12
2021/2/21 计算机算法设计与分析 12 滑动不会造成遗漏 ◼ KMP算法不再是将正文依次和模式中的 元素逐个地进行匹配，而是当出现“失 配”时从模式的第k(k=next(j))个元素开 始重新比较，这样会不会遗漏掉可以匹 配的子串呢？ ◼ 不会的。因为滑动的距离next(j)被定义为 满足p1…pk–1= pj–k+1…pj–1的最大的k