19 |字符串匹配

一、BF 算法(Brute Force,暴力匹配)

就是暴力循环查找，虽然复杂度比较高，但是却是经常使用的算法。
第一，实际的软件开发中，大部分情况下，模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以就停止了，不需要把 m 个字符都比对一下。所以，尽管理论上的最坏情况时间复杂度是 O(n*m)，但是，统计意义上，大部分情况下，算法执行效率要比这个高很多。
第二，朴素字符串匹配算法思想简单，代码实现也非常简单。简单意味着不容易出错，如果有 bug 也容易暴露和修复。在工程中，在满足性能要求的前提下，简单是首选。

二、RK算法（Rabin-Karp，n-m+1 ，比较适合已知子串长度的搜索）

在BF算法中，如果模式串长度为 m，主串长度为 n，那在主串中，就会有 n-m+1 个长度为 m 的子串，我们只需要暴力地对比这 n-m+1 个子串与模式串，就可以找出主串与模式串匹配的子串。

举例一：主串、模式串与匹配种类

主串为：{5，4，3，2，1}长度为5，模式串为{1}长度为1，则共有5种匹配
主串为：{5，4，3，2，1}长度为5，模式串为{2，1}长度为2，则共有4种匹配
主串为：{5，4，3，2，1}长度为5，模式串为{3，2，1}长度为3，则共有3种匹配
主串为：{5，4，3，2，1}长度为5，模式串为{4，3，2，1}长度为4，则共有2种匹配
主串长度-模式串长度+1=匹配种类
但是，每次检查主串与子串是否匹配，需要依次比对每个字符，所以 BF 算法的时间复杂度就比较高，是 O(n*m)。我们对朴素的字符串匹配算法稍加改造，引入哈希算法，时间复杂度立刻就会降低。
RK算法的思路是这样的：我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（这里先不考虑哈希冲突的问题，后面我们会讲到）。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。