V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
mightofcode
V2EX  ›  程序员

KMP 算法的一种解释

  •  
  •   mightofcode · 2020-01-11 20:32:33 +08:00 · 2944 次点击
    这是一个创建于 1538 天前的主题,其中的信息可能已经有所发展或是发生改变。

    KMP 算法很复杂,有很多解释方式( DFA,前缀后缀),下面是我的一种理解。

    我们在 s1 中匹配 s2,s1、s2 的长度分别为 N,M 1,首先我们按顺序匹配,直到匹配失败

    i 表示 s1 的匹配起始位置,j 表示 s2 的匹配位置

    image.png

    2,如果使用暴力搜索算法下一步将是这样的: image.png

    这样算法的复杂度是N*M 但是我们可以利用已经匹配到的字符串( AABAA )进行优化:
    image.png 3,由于 AABAA 是已知的与 s1 无关的信息,下一步我们可以做到匹配位置(红框)不变,i 向前跳过一些字符,j 变小,减少匹配长度
    这种情况一共有以下几种:
    image.png 可以看出来只有 C、D、E 是合法的(红框前面的部分必须匹配) 在 CDE 中我们只能选择 C,因为选择 D、E 会跳过 C 这个可能的正确匹配
    4,这里的 C 其实就是 AABAA 的最长前缀后缀匹配
    它满足:
    1,C 是一个前缀后缀匹配:AABAA 的长度为 n 前缀和长度为 n 的后缀相等
    2,C 是 n 最大的前缀后缀匹配
    image.png 5,在 j=5 的时候,最长前缀后缀匹配的长度为 2
    接下来要做的事情就是:
    i+=(j-2)=3
    j=2

    而 i+j=5,所以当前匹配位置维持在红框处不变

    6,所以只要我们计算出 s2 上面每个位置的最长前缀后缀匹配长度(前后缀匹配数组)就可以加速匹配过程了
    更详细的分析可以看出 KMP 算法的匹配过程时间复杂度是 O(N)的

    下面介绍如何计算前后缀匹配数组 preSuffixArr
    1,首先 preSuffixArr[0]=0, 这是因为前后缀匹配不能匹配自己
    2,然后 preSuffixArr[n]可以按照下面的规则递归计算
    首先取 v=preSuffixArr[n-1],代表前 n-1 个字符的最长前后缀匹配:
    如果 s2[v+1]==s2[n], 那么可以补上这个字符,构成一个长度为 n+1 的最长前后缀匹配
    如果 s2[v+1]!=s2[n], 继续对 v=preSuffixArr[v-1]计算这个过程

    下面示例介绍如何构造 AACAABAAA 的[前后缀匹配数组 preSuffixArr]

    k 表示当前计算位置,
    1,k=0,preSuffixArr[0]=0

    image.png

    2,k=1,然后由于 s2[0]==s2[1]="A",preSuffixArr[1]=preSuffixArr[0]+1 image.png

    3,k=2,v=preSuffixArr[1]=1, 由于 s2[2]!=s2[1],匹配失败 然后 v=preSuffixArr[v-1]=0, s2[2]!=s2[0], 匹配失败 preSuffixArr[2]=0 image.png

    ... 9,k=8,v=preSuffixArr[7]=2,s2[2]!=s2[8],匹配失败 image.png

    v=preSuffixArr[7]=2,s2[1]!==s2[8],匹配成功 image.png

    可以证明计算前后缀匹配数组的过程时间复杂度是 O(M)的,KMP 算法整体时间复杂度是 O(M+N)

    第 1 条附言  ·  2020-01-12 13:46:38 +08:00
    不知道图为啥挂了
    有兴趣的可以跳到 jianshu: https://www.jianshu.com/p/0f6b2e80eb51
    6 条回复    2020-01-13 11:38:20 +08:00
    WuMingyu
        1
    WuMingyu  
       2020-01-11 23:18:42 +08:00
    图挂了?当年上学还背过 KMP 算法,第二天就忘,现在就记得就是最大限度利用已知信息,还是那个通过 hash 匹配的算法好记
    xiexiping
        2
    xiexiping  
       2020-01-12 12:59:17 +08:00 via Android
    说实话,到现在都没完全搞明白这个算法
    mightofcode
        3
    mightofcode  
    OP
       2020-01-12 13:48:47 +08:00
    @xiexiping KMP 比较复杂,网上有很多解释,我想形成自己的一套理解能有助于理解 KMP 的本质
    lewis89
        4
    lewis89  
       2020-01-12 19:37:16 +08:00
    @mightofcode #3 理解没用 关键是要理解那个后缀表达式 ,后缀表达式 匹配到多少个字符 然后就能往前多走几个空格,这样可以减少时间复杂度,从可理解可实现的方式来讲 KMP 远没有 RK 就是一楼说的 hash 的那种方式快,或者在实现层面上好理解。
    pipapa
        5
    pipapa  
       2020-01-12 19:42:17 +08:00
    从状态机到 KMP 理解起来就很简单了
    Tubering
        6
    Tubering  
       2020-01-13 11:38:20 +08:00
    每次看了不超过两天忘得一干二净,再看再忘。放弃挣扎了已经
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3250 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 14:17 · PVG 22:17 · LAX 07:17 · JFK 10:17
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.