KMP算法是啥？
- 是字符串匹配算法，实现的功能是寻找在一个给定字符串A中字符串B的出现次数。
和暴力有什么区别？
暴力算法就是对于A中的每一个字符，一个一个的先与B中的第一个字符比较，如果匹配，则比较下一个字符和B中的第二个字符，如果全部匹配，则成功，如果失败，则继续比较下一个字符和A中的第一个字符。
这个算法在随机字符的情况下表现不错。因为第一个字符匹配的概率是1/26，第二个字符则是1/676…… 越往后，概率就会越小，因此期望匹配次数是A的长度k(几乎每一次匹配都会在第一个字母中终止)，也就是复杂度为O(k)。
但是，如果A中是由许多和B（设B的长度为n）在前n-1个字符都匹配的字符串组成的话，就会变得十分麻烦。这样每一次都要匹配第n次才会发现并不是一个匹配，复杂度将会上升到O(n*k)
对于这种最坏情况，KMP算法则有比较好的表现。
怎么做到的呢？
KMP算法记录了之前匹配的信息，就拿前面那个最坏情况的例子来说，假如你知道这n个字符和第一个字符都不匹配，就不用再用B的第一个字符和它们比较了，而是直接跳到第n+1个字符，或者假如这n-1个字符中有和B的第一个字符相同的字符，就跳到那个位置，节省了许多不必要的比较。
这个「之前匹配的信息」，就是用一个「部分匹配表」来维护的。
具体的实现方式分成了两部分
查找算法
m表示当前A中开始匹配的位置
i表示当前B中匹配成功的个数
最开始的时候，比较S[m+i]和W[i]，如果相同，则增加i
利用「部分匹配表」下一次寻找是从m+i-T[i]位置开始的（相当于是先跳到已经匹配过的所有字符的下一个，之后再「往回跳」T[i]个，到那个可以和B的前缀匹配的后缀上，其中T[i]已经预先处理好。），但是我们其实不必查找新的前T[i]个字符，因为我们已经比较过一遍了，因此直接使m=m+i-T[i],i=T[i]即可。
复杂度为O(n)，每次查找时要么i+1，要么往回跳T[i]个，显然T[i]<i，所以最多会运行2n次
发现今天写不完了，明天写Part2，以及KMP模版C++代码。