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

Question

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

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

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

Answer 1

其实类似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”。