用于解决字符串匹配问题
名词解释
前缀表
- 前缀：包含首字母不包含尾字母的所有子串
- 比如aabaaf的前缀有a aa aab aaba aabaa
- 后缀：包含尾字母不包含首字母的所有子串
- 比如aabaaf的后缀有f af aaf baaf abaaf
- 最长相等前后缀：比如aabaa，最长的，相等的，前缀和后缀相等，那么这个缀就是aa，长度是2
| 子串 | 最长相等前后缀长度 |
| ------------ | ------------ |
| a | 0 |
| aa | 1 |
| aab | 0 |
| aaba | 1 |
| aabaa | 2 |
| aabaaf | 0 |
于是前缀表就是0 1 0 1 2 0
巧妙的地方所在
- 最长相等前后缀，一定发生在两端(所以最长相等前后缀是几，就从后往前数几个，不会出现跳过某个的情况)！！！因为前缀要求包含首 后缀要求包含尾
- aabaa还可以匹配上，aabaaf匹配不上了，就找到f前面的最长相等前后缀“aa”,也就是说前面也有个aa，那么继续用这个aa匹配
- 相当于说，不用KMP，如果aabaaf匹配不上了，需要从索引1开始(第二个位置)继续匹配，但这是无效的，因为首是aa，所以KMP帮你跳到最近的有效位置
- 跳到的这个位置'b'下标是多少呢，刚好是2（最长相等前后缀长度）！！！
题解
匹配到f发现不匹配了，