KMP算法
解决字符串匹配问题
文本串aabaabaaf
模式串aabaaf
问：模式串是否在文本串中出现过？
1）暴力解法，ptr指向文本串index 0，遍历一遍发现不匹配，ptr再移向index 1，遍历……依次重复，直到ptr指向3
2）KMP算法，ptr指向文本串index 0，遍历到f发现不匹配，由于“aa”在字符串中index3和4时也出现过，因此ptr直接指向index 5
前缀表：
aabaaf的前缀指包括首字母不包括尾字母的组合： a, aa, aab, aaba, aabaa
最长相等前后缀指的是前缀和后缀相等的话，前缀/后缀长度为多少
| 模式串 | 最长相等前后缀 |
|---|---|
| a | 0 |
| aa | 1 |
| aab | 0 |
| aaba | 1 |
| aabaa | 2 |
| aabaaf | 0 |
| 如果从f开始不匹配（最长相等前后缀为0），那么就回到前缀后面的那个地方（也就是b），开始继续比对 |