KMP

• KMP由这三位学者发明的：Knuth，Morris和Pratt，所以取了三位学者名字的首字母

• KMP应用在字符串匹配上,KMP的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。

• 什么是前缀表?记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。也叫最长公共前后缀。next数组就是一个前缀表（prefix table）

• 前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

• 字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

• 前缀表工作原理：字符串（aabaa）的最长相等的前缀 和 后缀字符串是 子字符串aa ，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面重新匹配就可以了

• 前缀表使用解释
  要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。
  
  文本串中第六个字符b 和 模式串的第六个字符f，不匹配了。如果暴力匹配，发现不匹配，此时就要从头匹配了。
  但如果使用前缀表，就不会从头匹配，而是从上次已经匹配的内容开始匹配，找到了模式串中第三个字符b继续开始匹配。
  

• 前缀表与next数组，next数组既可以就是前缀表，也可以是前缀表统一减一（右移一位，初始位置为-1）。