其实类似KMP
之类的底层工具算法,很多都已经被封装在了各个语言的标准库,或者一些第三方库中。
拿你说的KMP
相关的字符串搜索算法来说,Python
的字符串有find()
、index()
等方法来搜索字串;Go
语言里标准库strings
也提供了Index()
函数来搜索字串,不过不太巧的是,这俩的底层用的都不是KMP
。
其中Python
使用了boyer-moore
和horspool
,在源码文件的注释中(.../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
}
所以你看,都不用什么开源框架,语言的标准库里就实现了这些算法。
然后你的第二个问题里最后的问题,为什么不用其他算法呢?Go
和Python
就告诉你:“我们就没用KMP
”。
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…