对KMP算法的疑问与理解
核心: 在逐字符遍历主串与模式串的过程中，发生失配时，不回溯主串的i字符指针，而是通过确定已经匹配过的模式串的子串的前缀集合与后缀集合的交集中最长元素的长度，来移动模式串的j字符指针，实现模式串的整体向右滑动，跳过绝不可能发生的字符串匹配,以此实现对朴素BF算法的优化
PMT: 部分匹配表(Partial Match Table),存放模式串的前缀集合与后缀集合的交集中最长元素的长度.
eg:
当index为6时，此时模式串为"ababab",
则前缀包括{a,ab,aba,abab,ababa},
后缀包括{b,ab,bab,abab,babab},
前缀与后缀集合的交集为{ab,abab}
则PMT值为"abab"的长度4
ababab
ababab
下面我们来看主串为ababababca与模式串 abababca的匹配
对于第一次匹配(a),主串在i处(index = 7)处失配，则主串和模式串的前边6位是完全相同的。
为什么能够用KMP算法来改进朴素的Brute-Force算法，通过移动j，来代替回溯i?
而不断左移或右移，得到的最终结果是相同的，故能使用KMP算法来进行改进。
设主串为T，模式串为P，那么回溯i，发生的三次首字符比较，实际上是
T[0] == P[0]?
T[1] == P[0]?
T[2] == P[0]?
可见，第一次比较发生失配，第二次比较首字符就不相等，应该跳过，第三次成功匹配。
为什么能够向右滑动?
=>首次匹配后能够确定主串i前的六个字符与模式串j前的六个字符是完全相同的，而这六个字符的最大相同前缀与后缀为abab，那么i前的四个字符就为六个字符的最大相同后缀abab，而j能够在滑动2个字符的距离后，使得j前的四个字符为六个字符的最大相同前缀abab
向右滑动的细节:
向右滑动的过程中会跳过一个b，这其实就是跳过的那一步
困扰笔者三天的问题与疑点:
为什么被跳过的字符位置，就是绝对不可能被匹配的情况?
=>让我们将目光重新放回到"字符串的前缀集合与后缀集合的交集中的最长元素"，即最长公共前后缀上。
被跳过的是第二种情况，即模式串向右滑动一格的情况。
而最长公共前后缀为abab，长度为4，模式串应该向右滑动两格(6-4=2)。
!! 意即，当模式串向右滑动[0,2)格时，无法实现最长公共前后缀的匹配，即使得模式串中j前对应的前缀abab滑动到主串i前的后缀abab处，使得最长公共前后缀匹配上。
因此，我们便能够确定模式串向右滑动一格时，
i前四个字符为abab，而与其对应的模式串的四个字符为baba，不匹配。
当模式串向右滑动两格时，
i前四个字符仍为abab，而与其对应的模式串的四个字符为abab，匹配。
式串向右滑动两格时，
i前四个字符仍为abab，而与其对应的模式串的四个字符为abab，匹配。