字符串匹配，也就是在一个字符串s中寻找是否存在子串substr的过程，可能是平时代码中最常用的函数之一，在golang中，是如何设计一种满足广大需求的字符匹配算法的呢？
基本流程
对于字符串s,和substr都很短的情况下，匹配规则很简单粗暴。 对于s很长substr很短走优化的BF算法（见下文），对于两个字符串都很长的情况，使用RabinKarp算法。
index源码
// Index returns the index of the first instance of substr in s, or -1 if substr is not present in s.
func Index(s, substr string) int {
n := len(substr)
switch {
case n == 0:
return 0
case n == 1:
return IndexByte(s, substr[0])
case n == len(s):
if substr == s {
return 0
}
return -1
case n > len(s):
return -1
case n <= shortStringLen:
// Use brute force when s and substr both are small
if len(s) <= 64 {
return indexShortStr(s, substr)
}
c := substr[0]
i := 0
t := s[:len(s)-n+1]
fails := 0
for i < len(t) {
if t[i] != c {
// IndexByte skips 16/32 bytes per iteration,
// so it's faster than indexShortStr.
o := IndexByte(t[i:], c)
if o < 0 {
return -1
}
i += o
}
if s[i:i+n] == substr {
return i
}
fails++
i++
// Switch to indexShortStr when IndexByte produces too many false positives.
// Too many means more that 1 error per 8 characters.
// Allow some errors in the beginning.
if fails > (i+16)/8 {
r := indexShortStr(s[i:], substr)
if r >= 0 {
return r + i
}
return -1
}
}
return -1
}
return indexRabinKarp(s, substr)
}
源码过程其实很简单。
假设在串s中匹配substr串，先计算substr长度,则：
- 为0，返回0
- 为1，使用
IndexByte计算，该方法从头开始以8位为1个字节比较substr是否在s中存在，存在返回下标，否则-1。 - 等于s的长度 return substr == s? 0 : -1
- 大于s的长度 返回
- 小于shortStringLen 走BF算法
- 否则 走RabinKarp算法
shortStringLen 大小根据机器来决定
var shortStringLen int
func init() {
if cpu.X86.HasAVX2 {
shortStringLen = 63
} else {
shortStringLen = 31
}
}
1 golang 字符串中匹配中的 BF 算法
BF算法，即暴风(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。
BF甚至算不上一个算法，golang中也只有当目标串和匹配串都很短的时候(在64位机器上长度小于64）,才会采用这个算法。如下，简单粗暴。indexShortStr实现方式有兴趣可参考/GOPATH/src/runtime/asm_amd64.s，这是一个汇编写的文件，技术有限并未深入追究，大致思路为简单BF算法。
case n <= shortStringLen:
// Use brute force when s and substr both are small
if len(s) <= 64 {
return indexShortStr(s, substr)
}
当目标串s较长，匹配串substr较短的时候，采用下面的优化算法：
- 在s中取子串t，t为s[:len(s)-len(substr) +1] ，其实这个操作就是取s的一个子串，假如substr有5个字符，则取s第一个字符一直到倒数第5个字符，如果substr有9个字符，则取到倒数第九个。
- t中使用indexbyte暴力查找substr第一个字符，如果找不到直接返回-1。因为s剩下的字符已经比substr短，不可能再匹配了，所以查找结束。如果找到了,假设下标为i，s子串t移动i个字符，然后比较s[i:i+n] == substr，相等则找到，否则失败次数加一，继续查找。
- 在步骤2种存在失败次数增加变量。失败次数影响为：
if fails > (i+16)/8 {
r := indexShortStr(s[i:], substr)
if r >= 0 {
return r + i
}
return -1
}
这里当失败次数增加到某个阈值时会触发条件if，如果触发，使用暴力匹配。
- i = [0,8) 允许失败2次 fails > 2触发
- i = [8,16) 允许失败3次 fails > 3 触发
- ...
实际上就是说从第一个字节开始允许失败2次，接下来每8个字符也就是每个字节间允许失败1次。
超过意味着什么呢？
超过此限制意味着substr的首字符在s开始部分经常出现，但是却不能完整匹配，继续此算法会多次触发整行匹配，效率不佳，因此放弃直接走暴力匹配路线。这里有个问题就是失败次数是如何选择的，优化点如何确定？后续可能会近一步研究。
总结一下这个优化的BF算法，就是取子串第一个字符在s中找，找到了就从当前位置匹配子串全部，否则确定找不到。优化点有两个，一是不是一个字符一个字符的匹配，而是如果某一段匹配失败次数过多直接放弃优化。
2. golang 中的RabinKarp 算法
BF只是解决了短字符匹配的问题，那么，对于长字符怎么处理呢？
在golang里面，长字符匹配采用RabinKarp来处理。
2.1 RabinKarp
RabinKarp伪代码：
1 function RabinKarp(string s[1..n], string pattern[1..m])
2 hpattern := hash(pattern[1..m]);
3 for i from 1 to n-m+1
4 hs := hash(s[i..i+m-1])
5 if hs = hpattern
6 if s[i..i+m-1] = pattern[1..m]
7 return i
8 return not found
对于一个些字符串匹配算法比如KMP，BM等，为了减少查找时间，通常选择加速跳过匹配错误字符策略，然而RabinKarp关注的重点不是加速跳过，而是加速子串相等性测试。
什么是加速子串相等性测试呢？通常来说，比较两个字符串相同的时间肯定比比较两个整数相等的时间长，如果能够通过某个hash函数将字符串转化为一个整数，那么比较速度将会得到巨大的提升。
但是天真的以为直接计算一个子串的hash来比较就可以的话就太天真了，直接计算一个长度为m的hash所需时间为O(m)，如果匹配串长度为n，那么算法复杂度为O(mn),和普通匹配没有区别。所以，怎样设计出在常数时间内计算出hash函数值的hash函数呢。
wiki上给出了一种trick：
The trick is the variable hs already contains the previous hash value of s[i..i+m-1]. If that value can be used to compute the next hash value in constant time, then computing successive hash values will be fast.
翻译过来，这个trick就是利用上一步算出来的hash计算下一步的hash。哎哟，还有这种操作？那么具体怎么写呢？wiki上介绍了了一种滚动hash算法（有兴趣可自行搜索），但是效果不太好。然而要作为一种运行广泛的流行语言，golang的hash必须要有高效率，那么他究竟是是怎么设计的呢。
// 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
}
sep就是需要计算hash的目标串，算法开始：
- 生成一个32位无符号0
- hash = hash*primeRK + uint32(sep[i])
唔，有点晕了，不急，推导一下试试看？
大家看好了，我要变形了！
哎呦，这不是那啥吗，对，就是那个多项式？no,no,no,我不是多项式，我是P进制啊。啊哈，hn分明就是以p为进制的一个数嘛。明白了，golang里面的hash函数计算方法就是生成一个以p为进制单位的数。恩，话是这样没错，可是下面还有一段代码做什么用的呢？思考一下，hash函数好像需要常数时间内完成吧，不对，不是好像，是必须！所以下面这段代码就是线索！
var pow, sq uint32 = 1, primeRK
for i := len(sep); i > 0; i >>= 1 {
if i&1 != 0 {
pow *= sq
}
sq *= sq
}
恩~
i 取 seq 长度，当i二进制最后一位为1的时候，pow 乘上一个sq，而这个sq在每一次迭代的时候都自乘，初始值为pk。。。。。。
有经验的同学可能一眼看出这段代码干啥的，但是对于没有见过的同学来说乍看可能有点费解。如果一眼不太容易看出来先放着，既然是线索那么后续还有他出场的地方。
RabinKarp算法golang实现
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++ {
h = h*primeRK + uint32(s[i])
}
if h == hashss && s[:n] == substr {
return 0
}
12行 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
}
先理解一下12行之前的代码，先计算子串hash和目标串hash,然后比较hash，最后比较字符串。
这里存在几个问题。
第一，为什么hash比较相等了又要比较串呢？这样子效率怎么提升呢？
第二，为什么子串hash用hash函数，而目标串重新使用hash函数部分代码却不调用hash函数呢？
第一个问题很简单，hash值相等了不一定字符串相等
，因此需要比较一次串确保相等。而效率问题需要回头想一下RabinKarp算法的实现，比较串的行为发生在hash比较之后，而比较hash仅需一次计算，而大部分比较基于是hash值得比较，因此函数效率可以得到保障。但是需要注意的是，如果hash函数选的不恰当，那么hash冲突会很多，则字符串比较次数相应增加，因此算法效率也会急剧降低。
第二个问题明显需要理解pow这个变量，思考RabinKarp算法，为了加快hash生成速率，需要根据第一个hash，在常数时间内计算出下一个hash。
而pow这个变量仅仅是用了一次在 h -= pow * uint32(s[i-n])这句代码，什么意思呢？
看看之前的操作，h *= pk,h += uint32(s[i])，
这两句话等价于
h = h*pk + uint32(s[i])....
这句话似曾相识，这不就是hash算法里面的令人脑壳痛的进制转换嘛。
s[i - n] 在第一次运行循环的时候即s[0],也即第一个字符，既然hash求的是 1 ~ n-1 的串的p进制，那么如果要求 2 ~ n 的p进制，则需要把第一个项删掉，然后所有后面的数字左移一位，接着再进行 h = h*p + c的操作。nice,又到了我们的变形时间了！
假设从 1 ~ n 需要经过推导1的过程，那么 2 ~ n+1 需要经过推导2的过程，于是
hn+1 = hn * p + cn+1 - c1 * p ^ n
哎哟，先乘后加再减，完美契合。
hn +1 对应 下一个hash
hn 对应上一个hash
cn+1 代表新加入的字符
c1 代表第一个字符
所以说这个pow就是p的n次方！也就是说上面的线索就是求一个幂的操作。。。
原来求幂还可以这样写的吗？学到了。。
总结，golang的RabinKarp算法利用特殊p进制生成hash函数，这个函数可利用上一次生成的hash值乘以p加上最后一个字符减去第一个字符乘以p的n次方的得值来得到，实现了在常数时间内计算hash的功能。
2.2 rk算法疑惑
虽然算法明白了，但是有几个值得注意的地方。
// primeRK is the prime base used in Rabin-Karp algorithm.
const primeRK = 16777619
算法中用到了一个进制数，为什么要用这个数来做进制呢，这里面又藏着什么秘密呢？
我们知道了 RK算法只是加速子串匹配速度，并不会加速移除坏的字符速度，那么能不能有一种合适的hash算法适应移除过程呢？
虽然常数时间内完成了hash，然而优势在哪呢，这个hash效率对比其他匹配如KMP，BM又有何特点呢
且看研究二。
