引用后缀的目的：
“ABBABA” 如果说ABA里面组成的AB是答案组成部分的开头，那么AB后面的字符一定是和模式串开头的第三个字符一样，如果不一样一定不是答案的组成，所以我们需要后面字符进行判断，故引用后缀
引用前缀的目的：
在公共前后缀中，后缀=前缀。前缀=模式串匹配的前几个字符，要保证后缀是答案的组成，则必须让后缀的前几个字符=模式串匹配的前几个字符。即保证后缀=前缀。故引用公共前缀是一个正确的选择
综上，只要是存在公共前后缀则前面已经匹配的串中一定是部分机会组成答案的，且最长公共前后缀一定包含子公共前缀，故选择 最长公共前后缀 最长公共前缀一定唯一，且从匹配成功的最后一个点开始
由于最长公共前缀唯一或无最长公共前缀，故每次只会移动一次。若有公共前缀则已经知道前面是匹配的故j指针不会回溯到0，而是回溯到公共前缀的下个字符继续匹配。若无公共前缀则则匹配第一个字符，其实总结来说是一个通用的过程， 若当前字母匹配不成功则发生移动，若公共前缀长度为n，则将模式串j指针移动到n+1与主串当前位比较（ 有一种特殊情况，匹配不成功，公共串长度为0，且此时模式串字母为第一个，由于移动之前就是该字母和主串当前字母不相同，而移动后会再次回到1字母这样就造成了无限循环，故应该将主串也要移动下一位）
模式串移动方式为以下
ne[i] = 1 && i == 1 { j++; compare(s[i],s[j]) }
ne[i] = x (x!=1) && i==y { i==x; compare(s[i],s[j]) }
ne[i] == n+1
Original: https://www.cnblogs.com/lbqverdent/p/15884282.html
Author: verdent
Title: KMP分析证明
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/582017/
转载文章受原作者版权保护。转载请注明原作者出处！