字符串匹配

indexOf  底层就是使用字符串匹配算法

字符串匹配算法很多

BF( Brute Force)算法

    暴力匹配算法，也叫朴素匹配算法，从名字上看出这个算法很暴力，当然它也很好理解，但是性能不高。

    BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。

    用一句话来概括，那就是，我们在主串（比如在字符串A中查找字符串B，那字符串A就是主串，字符串B就是模式串）中，检查起始位置分别是0、1、2…n-m且长度为m的n-m+1个子串，看有没有跟模式串匹配的。

    每次都比对m个字符，要比对n-m+1次，总共要进行 m*(n-m+1)次比较，所以，这种算法的最坏情况时间复杂度是O(n*m)。

    虽然这钟算法的时间复杂度很高，但是在开发中经常使用到，原因有2：

        1.在开发中，主串的和模式串的长度并不会太长，所以 O(n*m) 的时间复杂度并不会太大；

        2. BF 算法比较简单，不易出错。

---

RK （Rabin-Karp）算法

        它是以 两位发明者的名字命名的算法，它是 BK 算法的升级。

        我们知道 BK 算法的时间复杂度是 O(n*m)，RK 算法对 BK 算法稍加改造，引入 哈希算法，我们通过哈希算法对主串中的n-m+1个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（这里先不考虑哈希冲突的问题）。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。

        但是在求解主串中的每个字串的哈希值的时候，我们需要遍历子串的每个字符，尽管模式串 和 子串 比较的效率提高了，但是算法整体效率并没有提高。此时，我们需要将我们哈希算法尽可能地设计地更有技巧一点。

---

BM（Boyer-Moore）算法

    BM 算法比较复杂，它包括两部分，分别是 坏字符规则（bad character rule）和 好后缀规则（good suffix shift）。

    坏字符规则（bad character rule）

---

KMP （Knuth Morris Pratt）算法

    它是以 三位发明者的名字命名的算法，KMP 算法 的本质上 和 BF 算法 是一样的，但是在过程中，优化了很多不必要的比较。

    在 BF 算法中，我们采用暴力的枚举方法，将所有的 子串 都和  模式串 做了比较，但是这个过程中其实有很多非必要比较的，比如