字符串匹配算法基础版
最近小谭又被问了一个问题，编程语言中的字符串匹配函数是怎么实现的，是啥原理。
看来大猫又要展示他靠才华吃面的大招了。
小谭一边心里犯嘀咕，这还能有啥原理，直接用不就行了，管那么多干啥，一边对大猫说，今天又想要吃啥面了。
大猫就是这样，经常问你一个问题，你要不会，然后让你请他吃碗面，他给你讲清楚。
大猫腼腆一笑表示今天吃一碗拉面就行，估计是今天这个大招的技术含量不够高吧，一碗拉面就给应付了。
果然，大猫仅用 5 个字就形容了他的大招，暴力匹配法，小谭一听暴力法，眉头一皱，貌似也想到了答案，大猫赶紧继续补充。
暴力匹配就是用最原始、最笨的方法去匹配，把两个字符串分别称作目标字符串和模式字符串，然后要判断在目标字符串中能否匹配到模式字符串。
小谭灵光一闪，迫不及待的说出了自己的思路，这个简单啊，不就是从目标串第一个字符和模式串的第一个字符开始比较，如果两个字符相同，则继续比较两者后面的字符，否则，将模式串移动到目标串的第二个字符重新开始比较。
大猫有点着急了，眼看自己的大招已然被识破，赶紧顺势总结了一番。
是哒，这就是最常规的思路，也是最简单的算法，这个暴力匹配算法被称作 BF (bure force) 算法。
小谭依然追问到，这个算法没啥技术含量，就是用的笨方法，还有没有更好一点的，不然都不值这碗拉面。
有，还真有比这更好一点的，不过要加个卤蛋才可以。看样子大猫早就准备好的了，满满的套路。
我们可以使用哈希算法来优化 BF 算法，大猫看起来很得意的样子。
为啥要用哈希呢，怎么用，小谭有点不太明白。
你看在 BF 算法中，每次都是拿目标字符串和模式串一个字符一个字符的比较，这样很耗时间。
如果目标串的长度为 a，模式串的长度为 b，那么目标串其实就可以拆成 (a-b+1) 个子串…
等等，为啥是 (a-b+1) 呢，小谭有点疑惑。
我给你画张图你就明白了，大猫边说边开始在手机上画起了图。
目标串长度为6，模式串长度为3，所以目标串一共有4个子串
接下来其实就是把这 (a-b+1) 个子串和模式串挨个比较即可。
那这里也没有特别的啊，也没用到哈希函数啊，小谭紧接着问大猫。
别急啊，关键就在下面的哈希函数了，我们把目标字符串中的每个子串和模式串都使用一个哈希函数来获得哈希值，然后我们就可以直接比较其对应的哈希值就可以了，由于哈希值是一个数字，数字之间的比较是很快的。因此，判断模式串是否在目标串中，只需要比较两者是否有相等的哈希值就好了。
这个思路有点巧妙啊，小谭有点茅塞顿开的感觉了。
这其实只是一个思路，核心在于这个哈希函数的设计，比如如果存在哈希冲突怎么处理，怎么只遍历一次目标串即可算出所有子串的哈希值，这些都是这个哈希函数要解决的问题，另外这种算法叫做 RK 算法，是两位外国人名字的首字母组合而成。
这碗拉面总算是值了，不过最后这个哈希函数的具体设计下回还得继续讲清楚啊。。。
没问题啊，不过我也还得回去再查查资料重新学习下，争取下回给你讲明白，今天给你讲的就是个主要的思路。。。
。。。
推荐文章：
腾讯云开发者
