因为这周事情特别多，所以上个星期所教的字符串匹配现在才进行整理。上周我们主要学习了四个算法：暴力算法，sunday算法，rk算法和kmp算法。本次主要讲一下上周师兄没来得及将的KMP算法，暴力算法是一切的基础所以顺便提一下。
首先，什么是字符串匹配？
如图所示，简而言之字符串匹配就是在text字符串中寻找pattern出现的位置。
一、暴力算法
暴力算法应该是绝大多数人第一时间想到的第一个方法了，其核心思想可以理解为：
一步步移动text字符串，直到“上方的”text字符串相对应位置的字符与pattern一一对应为止。（为什么说是移动text字符串而不是移动pattern字符串？因为在代码的实现上，pattern每次都是从0位置开始，变化的是text字符串的比较位置，所以说text字符串移动更有助于理解代码）
如下图所示：
第一次比较，text字符串的第一个字符为B，pattern为A，匹配失败。
第二次比较，将text往左移动一位，此时text的第二个字符将与pattern的第一个字符比较，本次比较仍然没有对应。
直到第四次比较，两个字符串对应位置的字符终于匹配成功。这样就可以让text停止移动，依次比较接下来几位对应位置的字符。如果匹配都成功，结果就出来了。
二、KMP算法
可以看出，暴力算法的比较次数很多，如果比较失败了，下一次比较pattern还得从第0位开始比较，那么有什么办法可以让字符串比较的时候比较智能的跳过一些无意义的比较呢？KMP算法就是解决这个问题的。
下面就来说明下KMP算法是什么。
如图所示，当我们匹配到第六个字符的时候，我们发现text是B，而pattern是A，匹配显然失败了，如果是按照暴力算法，我们就要将text往左边移动一位。
然而，我们可以观察到，pattern比较失败的那个字符A前面（ABBAB）中，往前找和往后找，可以找到两个一样的字符串（AB），这就给字符串提供了一个跳板，将前面AB原本在的位置直接跳到后面AB原本在的位置，就可以一下次移动很多位，极大减少了比较的次数，而且中间不会有遗漏的情况。
那么，这些相同的前缀后缀是怎么找到的，我们如何在代码中知道他们应该跳多少步？
如下图所示，如果我们假设pattern第一个字符就不匹配，而我上面提到，要往左边找相同的前缀字符串和后缀字符串，但第一个字符前面什么都没有，所以下一次仍然要从第一位开始找起来。
同理，当第二个字符不匹配的时候，前面只有一个字符，也找不到两个相同的前后缀，所以仍然要从第一个找起。
直到匹配到第四个字符，我们终于可以分别从前从后找到两个相同的字符串了。那就是第1位的A和第3位的A。
然后，因为前缀和后缀相同，而且比较到第四个字符，说明前面三个字符都是匹配成功，我们将会做这样的移动，移动过后，原本的比较到的第4位字符变成了第2位了。第1位A原本的位置就是曾经的后缀A匹配成功的，所以无须比较。故可以得出接下来要从第二位开始找起。
同理，接下来第五位，我们可以找到AB与AB，移动后比较的位置变成第3位。
而到了第六位的时候，我们可以找到第一位的A和第五位的A，但是我们还可以找到第123的ABA和第345的ABA，此时我们应该【选最长】的。
接下里你们可以自己在纸上写一写接下来的结果。
以此类推可以得到以下结果。
转化为坐标迁移数组：
是不是很眼熟？《数据结构》这个书本里面的坐标迁移列表就是这么出来的。接下来只要应用到代码中就可以了。
具体的代码网络上有很多，可以自己去搜索试着试验一下。
