leetcode之28实现strStrGolang(KMP算法)

2021-03-26 21:25

阅读:664

标签:Golan   span   其他   理解   说明   利用   lazy   dex   exp   

KMP算法

举例

假设我们有字符串:

GTGTGAGCTGG

并且有模式串

GTGTGCF

算法解析

  • 我们需要创建模式串的next,他表示当两个字符串进行模式匹配失败的时候,需要从模式串的哪一个位置重新开始匹配

    • 例如上面两个字符串

      0 1 2 3 4 5 6 7 8 9 10
      G T G T G A G C T G G
      G T G T G C F        

      我们可以看到在下标为5的地方匹配失败了,因为字符串中的字符是A,而模式串中的字符是C

      但是我们不需要再从模式串的开始的地方重新匹配,我们只需要从如下的地方重新开始

      0 1 2 3 4 5 6 7 8 9 10
      G T G T G A G C T G G
          G T G T G C F    

      此时在原始字符串中的下标位置没有变,但是模式串的匹配开始的地方不再是0了,而是从第4个字符开始匹配的,也就是用模式串中处于坐标3T与原始字符串中处于下标5的进行比较

      那么我们是怎么得到这个下标3的呢?没错就是通过next数据

    • 总的来说,next数组保存的是这样的数据:

      例如模式串GTGTGCF,那么next[5]保存的就是在模式串下标5前面的字符串中,位于开始位置的字符串和末尾位于5之前的字符串相同时,这个字符串的长度就是next[5]的值

      技术图片

      如同上图,同一个子串,他们在模式串的两端,那么,这个子串的长度就是next[]的值了,当然,这两个子串不能完全重叠,不然这一切就失去了意义

  • 我们利用这next数组,来减少字符比较的次数,当比较字符失败时,就根据next换到新的位置,这个位置就是next的值

  • 或许这样你可以想通,因为如上图所示,位于模式串首位两端的子串是一样的,而整个模式串都是比较成功的,所以当我们比较模式串的下一个字符,完全可以把前面的子串挪到最后来,那么是不是就说明了前面这部分子串的内容是不需要再次比较的了

伪代码

  • 构建next数组,一直模式串sModel

    • 设置next[0]=-1

    • index=0,k=-1,开始循环到len(sModel)-2

    • 如果k==-1 || sModel(index)===sModel(k)

      • next[++index]==++k

    • k=next[k]

      其实这一步是好理解的,当我们已经知道了next[i]的值为k,意思就是说在i之前的模式串中(最后一个字符下标是i-1),开始的k个字符(最后一个字符下标是k-1)和结束的k个字符是一样的

      • 那么如果sModel[i]==sModel[k],是不是就是说在i+1之前的模式串中,开始的k+1个字符和结束的k+1个字符是一样,那么也就是说next[i+1]在这种情况下就等于next[i]+1

      • 如果sModel[i]!=sModel[k],那么我们就不能像上面那样加1了,我们此时将k设置为next[k],这一步这样理解,因为对于前k个字符的模式创中,位于开始的next[k]个字符和位于结束的next[k]个字符是一样的,并且在前i个模式串字符中,前k个字符和结束的k个字符是一样的,那么我们就一定有前i个字符的模式串中,前next[k]个字符和位于结束的next[k]个字符是一样的,所以我们只需要比较第next[k]+1个字符(下标为next[k])和第i+1个字符(下标为i)是否相同即可。而这个处理又回到了我们的上一步循环。

    • 如果k=next[k]时的结果是k=-1,那么我们就直接将next[index]的值弄为0就可以了,这表示我们需要从模式的第一个元素重新开始匹配,而next[0]=-1表示如果第一个字符就不匹配你,我们就要从第-1个字符开始匹配,然而没有-1这个元素,所以我们需要移动到主串的下一个字符

  • 进行模式匹配

    • 有了next数组以后,我们就进行匹配,

      • 当匹配成功以后就检查是否到了模式串的末尾,

        • 如果没到就继续匹配

        • 如果到了就输出

      • 当匹配到模式串的下标index失败以后,就从从模式串的next[index]的位置重新开始匹配

        • 如果next[index]>=0,那么不移动主串的下标,直接开始匹配

        • 如果next[idnex],那么就将主串的下标后移以为,从模式串的开头重新开始匹配

实现strStr

他返回模式匹配成功以后的开始的下标

很容易,就是在模式匹配成功的时候,用主串的下标减去模式串的下标(模式串此时的下标就是模式串的长度减1)

注意:考虑边界条件,比如主串为空或者模式串为空,甚至两个都为空

代码:

    // next数组
    next := make([]int, len(needle))
    // 构建next数组的函数
    createNext := func() {
        // 当模式串长度为0,就直接返回
        if len(needle) == 0 {
            return
        }
        // 默认next[0]=-1
        k, index := -1, 0
        next[0] = -1
        // 使用模式串倒数第二个字符计算最后一个字符的next值,所以这里是

  

 

leetcode之28实现strStrGolang(KMP算法)

标签:Golan   span   其他   理解   说明   利用   lazy   dex   exp   

原文地址:https://www.cnblogs.com/gyyyl/p/13680172.html


评论


亲,登录后才可以留言!