蒂花之秀 --- 大神用漫画讲解字符串匹配算法，让你噩梦变美梦
第二轮，我们把模式串后移一位，从主串的第二位开始，把主串和模式串的字符逐个比较：
主串的第二位字符是 b，模式串的第二位字符也是 b，两者匹配，继续比较：
主串的第三位字符是 b，模式串的第三位字符也是 c，两者并不匹配。
第三轮，我们把模式串再次后移一位，从主串的第三位开始，把主串和模式串的字符逐个比较：
主串的第三位字符是 b，模式串的第三位字符也是 b，两者匹配，继续比较：
主串的第四位字符是 c，模式串的第四位字符也是 c，两者匹配，继续比较：
主串的第五位字符是 e，模式串的第五位字符也是 e，两者匹配，比较完成！
由此得到结果，模式串 bce 是主串 abbcefgh 的子串，在主串第一次出现的位置下标是 2：
以上就是小灰想出的解决方案，这个算法有一个名字，叫做 BF 算法，是 Brute Force（暴力算法）的缩写。
上图的情况，在每一轮进行字符匹配时，模式串的前三个字符 a 都和主串中的字符相匹配，一直检查到模式串最后一个字符 b，才发现不匹配：
这样一来，两个字符串在每一轮都需要白白比较 4 次，显然非常浪费。
假设主串的长度是 m，模式串的长度是 n，那么在这种极端情况下，BF 算法的最坏时间复杂度是 O（mn）。
————————————
比较哈希值是什么意思呢？
用过哈希表的朋友们都知道，每一个字符串都可以通过某种哈希算法，转换成一个整型数，这个整型数就是 hashcode：
hashcode = hash（string）
显然，相对于逐个字符比较两个字符串，仅比较两个字符串的 hashcode 要容易得多。
给定主串和模式串如下（假定字符串只包含 26 个小写字母）：
第一步，我们需要生成模式串的 hashcode。
生成 hashcode 的算法多种多样，比如：
按位相加
这是最简单的方法，我们可以把 a 当做 1，b 当做 2，c 当做 3......然后把字符串的所有字符相加，相加结果就是它的 hashcode。
bce = 2 + 3 + 5 = 10
但是，这个算法虽然简单，却很可能产生 hash 冲突，比如 bce、bec、cbe 的 hashcode 是一样的。
转换成 26 进制数
既然字符串只包含 26 个小写字母，那么我们可以把每一个字符串当成一个 26 进制数来计算。
bce = 2*(26^2) + 3*26 + 5 = 1435
这样做的好处是大幅减少了 hash 冲突，缺点是计算量较大，而且有可能出现超出整型范围的情况，需要对计算结果进行取模。
为了方便演示，后续我们采用的是按位相加的 hash 算法，所以 bce 的 hashcode 是 10：
第二步，生成主串当中第一个等长子串的 hashcode。
由于主串通常要长于模式串，把整个主串转化成 hashcode 是没有意义的，只有比较主串当中和模式串等长的子串才有意义。
因此，我们首先生成主串中第一个和模式串等长的子串 hashcode，
即 abb = 1 + 2 + 2 = 5：
第三步，比较两个 hashcode。
显然，5！=10，说明模式串和第一个子串不匹配，我们继续下一轮比较。
第四步，生成主串当中第二个等长子串的 hashcode。
bbc = 2 + 2 + 3 = 7：
第五步，比较两个 hashcode。
显然，7！=10，说明模式串和第二个子串不匹配，我们继续下一轮比较。
第六步，生成主串当中第三个等长子串的 hashcode。
bce= 2 + 3 + 5 = 10：
第七步，比较两个 hashcode。
显然，10 ==10，两个 hash 值相等！这是否说明两个字符串也相等呢？
别高兴的太早，由于存在 hash 冲突的可能，我们还需要进一步验证。
第八步，逐个字符比较两字符串。
hashcode 的比较只是初步验证，之后我们还需要像 BF 算法那样，对两个字符串逐个字符比较，最终判断出两个字符串匹配。
最后得出结论，模式串 bce 是主串 abbcefgh 的子串，第一次出现的下标是 2。
什么意思呢？让我们再来看一个例子：
上图中，我已知子串 abbcefg 的 hashcode 是 26，那么如何计算下一个子串，也就是 bbcefgd 的 hashcode 呢？
我们没有必要把子串的字符重新进行累加运算，而是可以采用一个更简单的方法。由于新子串的前面少了一个 a，后面多了一个 d，所以：
新 hashcode = 旧 hashcode - 1 + 4 = 26-1+4 = 29
还未添加个人签名 2021.10.31 加入
还未添加个人简介
评论