分享

白话 KMP 算法

 dinghj 2019-03-19

KMP 算法是计算机字符串匹配的常规算法。wiki
本篇文章借助简单示例,用通俗易懂的方式描述对 KMP 算法的理解。

匹配值表

对于 KMP 来说,“匹配值表”是很关键的。下面我们从简单示例出发描述匹配值表是如何产生的,以便理解。

现在 我们需要查找的字符串是 “ABABABCA”。

在描述“匹配值表“之前,我们需要简短的介绍下前缀和后缀的概念:

前缀:从 0 位,依次截取 1 到(len - 1)长度字符串的集合
后缀:从 len - 1 位反序,依次截取 1 到(len - 1)长度字符串的集合

字符串 前缀集合 后缀集合 前缀后缀交集
"A" [] [] []
"AB" [A] [B] []
"ABA" [A,AB] [A, BA] [A]
"ABAB" [A, AB, ABA] [B, AB, BAB] [AB]
"ABABA" [A, AB, ABA, ABAB] [A, BA, ABA, BABA] [A, ABA]
"ABABAB" [A, AB, ABA, ABAB, ABABA] [B, AB, BAB, ABAB, BABAB] [AB, ABAB]
"ABABABC" [A, AB, ABA, ABAB, ABABA, ABABAB] [C, BC, ABC, BABC, ABABC, BABABC] []
"ABABABCA" [A, AB, ABA, ABAB, ABABA, ABABAB, ABABABC] [A, CA, BCA, ABCA, BABCA, ABABCA, BABABCA] [A]

从上表,如果耐心看,完全可以理解前缀和后缀的概念。

那么“匹配值”又是指什么呢?

“匹配值”是指前缀和后缀集合,最长共有元素的长度,即交集中最长元素的长度

那么不难从上表中得出每一位(index)字符对应“匹配值(value)”:

char: | A | B | A | B | A | B | C | A |
index:| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
value:| 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |

匹配值表的使用

我们可以根据匹配值表来加速查找匹配的过程。

下面还是举例说明问题:

在字符串"BACBABABAABCBABABABCA"(text)中查找上文中的字符串"ABABABCA"(pattern),
下文中对两个字符串的代称为括号之内的单词。

从 text 第一位开始匹配,第一次匹配成功是这样:

BACBABABAABCBABABABCA
 |
 ABABABCA

那么开始往后匹配,发现 text 的第二位"C"和 pattern 的第二位"B"不匹配,
所以当前部分匹配长度为1(只有一个A),并且根据上文的匹配值表得到,当前的匹配值为 0。

移动位数 = 已匹配字符长度 - 对应位的匹配值

即 移动位数 = 1 - 0,所以我们继续向后移一位进行匹配。

再一次匹配成功的情形:

BACBABABAABCBABABABCA
    |||||
    ABABABCA

此时,text 中的"A"与 pattern 中的 "B" 不匹配,如果不按照算法,肯定是继续后移一位进行匹配。
如果根据上述计算公式:

移动位数 = "ABABA".length - pattern[4]的匹配值
即 5 - 3 = 2

所以我们可以一次后移两位:

BACBABABAABCBABABABCA
    xx|||
      ABABABCA

又不匹配了,此时应该后移
"ABA".length - pattern[2]的匹配值
即 3 - 1 = 2

继续后移两位:

BACBABABAABCBABABABCA
      xx|
        ABABABCA

继续后移
"A".length - pattern[0]的匹配值
即 1 - 0 = 1

后移一位:

BACBABABAABCBABABABCA
        x||
         ABABABCA

继续后移
"AB".length - pattern[1]的匹配值
即 2 - 0 = 2

后移两位:

BACBABABAABCBABABABCA
         xx|
           ABABABCA


第一位都不匹配,我们继续往后移动直到匹配成功

BACBABABAABCBABABABCA
             ||||||||
             ABABABCA

移动几次之后(step=1),找到了最终匹配结果。

参考:
http:///blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。
    转藏 分享 献花(0

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多