KMP 算法的实际应用有哪些?

Gjjhgfrrgugv2020
  • 3
新手上路,请多包涵

想问下 KMP 算法的实际应用有哪些?

  1. 比如说,某某开源框架的某某实现有具体应用到吗?
  2. 比如说,在你的工作中,有实际使用过 KMP 算法吗?是引用了包,还是自己写了一套实现?是基于什么要考虑使用这个算法,而不是使用别的算法?

Google 了一下相关的,很多都是写怎么实现 KMP 的,搜不动了,特意提个小问题。

回复
阅读 2.3k
1 个回答
杜秉轩
  • 1.3k
✓ 已被采纳

其实类似KMP之类的底层工具算法,很多都已经被封装在了各个语言的标准库,或者一些第三方库中。

拿你说的KMP相关的字符串搜索算法来说,Python的字符串有find()index()等方法来搜索字串;Go语言里标准库strings也提供了Index()函数来搜索字串,不过不太巧的是,这俩的底层用的都不是KMP

其中Python使用了boyer-moorehorspool,在源码文件的注释中(.../Objects/stringlib/fastsearch.h)是这么描述的

/* fast search/count implementation, based on a mix between boyer-
   moore and horspool, with a few more bells and whistles on the top.
   for some more background, see: http://effbot.org/zone/stringlib.htm */

Go语言则使用了Rabin-Karp算法,直接把核心源码贴出来好了:

// primeRK is the prime base used in Rabin-Karp algorithm.
const primeRK = 16777619

// hashStr returns the hash and the appropriate multiplicative
// factor for use in Rabin-Karp algorithm.
func hashStr(sep string) (uint32, uint32) {
    hash := uint32(0)
    for i := 0; i < len(sep); i++ {
        hash = hash*primeRK + uint32(sep[i])
    }
    var pow, sq uint32 = 1, primeRK
    for i := len(sep); i > 0; i >>= 1 {
        if i&1 != 0 {
            pow *= sq
        }
        sq *= sq
    }
    return hash, pow
}

func indexRabinKarp(s, substr string) int {
    // Rabin-Karp search
    hashss, pow := hashStr(substr)
    n := len(substr)
    var h uint32
    for i := 0; i < n; i++ {
        // primeRK is the prime base used in Rabin-Karp algorithm.
        h = h*primeRK + uint32(s[i])
    }
    if h == hashss && s[:n] == substr {
        return 0
    }
    for i := n; i < len(s); {
        h *= primeRK
        h += uint32(s[i])
        h -= pow * uint32(s[i-n])
        i++
        if h == hashss && s[i-n:i] == substr {
            return i - n
        }
    }
    return -1
}

所以你看,都不用什么开源框架,语言的标准库里就实现了这些算法。

然后你的第二个问题里最后的问题,为什么不用其他算法呢?GoPython就告诉你:“我们就没用KMP”。

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏