前言

一切都要从 LeetCode 的第 28 题 实现 strStr() 开始说起，当自己脑子里的第一种暴力查找法写出来并 AC 之后，还是觉得不满足，决定把能找到的解法都理解了，于是便有了这个系列。

字符串匹配的整体思路

当我理解完四种经典的匹配算法之后，总结了一下这类操作的核心：

1. 将 模式串 和 主串 进行比较
   • 从前往后比较
   • 从后往前比较
2. 匹配时，比较 主串 和 模式串 的下一个位置
3. 失配时，在 模式串 中寻找一个合适的位置
   • 如果找到，从这个位置开始与 主串 当前失配位置进行比较
   • 如果未找到，从 模式串 的头部与 主串 失配位置的下一个位置进行比较

所以总的来说，之所以会有这么多种匹配算法，本质上就是一些大神对第1步和第3步进行了优化， 这个核心思路一定要牢牢的先记在脑子里 ，这样之后理解优化的匹配算法就不会一脸懵逼。

算法介绍与分析

介绍

BF 算法，Brute-Force(暴力)法的简称，完全没有优化，每次失配时从 主串 的下一个位置进行比较，直到比较结束。

分析

算法描述如下：

1. 将 模式串 和 主串 从前往后比较
2. 匹配时，比较 主串 和 模式串 的下一个位置
3. 失配时，从 主串 的 下一个位置 开始与 模式串 的头部重新开始比较

我们假设有 主串 ABABBBAAABABABBA 和 模式串 ABABABB ， 下面放五张图来理解一下这个过程：

上面这两幅图，表现的是第1步和第2步，可以看出：

1. 从 S[0] 和 P[0] 开始从头往后比较
2. 如果匹配，比较 S[i++] 和 S[j++]

上面这两幅图，则表现的时第3步，可以看出：

1. 如果 S[i] 和 P[j] 失配
2. j = 0 从 P[0] 也就是 模式串 头部开始与 主串 的 下一个位置 S[i - (j - 1)] 开始继续进行匹配

重复上述两步，直到下图完全匹配或者找不到模式串为止

代码

思路还是很好理解的，但是代码怎么写呢？ 其实我一直觉得刷 LeetCode 除了巩固与提高 数据结构与算法 的能力之外，最重要的就是训练一种 把思路翻译成代码的能力 ，下面我来尝试翻译一下上述的算法思路。

1、先进行极端情况的排除

这个操作应该是刷题刷多了，像以前做数学题写“解”的操作

2、写出整体的结构

1. 从算法的思路很容易看出，这里的“重复上诉两步”，明显是要翻译成循环操作
2. 如果是循环，那么终止条件是什么，可以很快想到，只有两种终止情况：
   • 主串 中没有找到 模式串 的匹配，此时 i = haystack.length
   • 主串 中找到了 模式串 的匹配，此时 j = needle.length
3. 算法处理过程主要是两步，所以这里一定有一个分支结构
   • 匹配
   • 失配
4. 如果没找到，直接 return -1 就好了，但要是找到了，应该怎么确定那个 index 的值呢？根据上面成功的图，我们可以发现，匹配的位置 8 ，是等于 主串 的末尾 14 减去 模式串 的末尾 6 得到的，也就是最后匹配的那个 index = i - j