那我们不妨观察下，上次匹配失败的情况，当文本串中“$”与模式串中“D”不匹配时，我们其实已经完成了6次匹配，也就是说我们在文本串和模式串中已经找到了"ABCDAB"。同时我们可以发现模式串中前缀“AB”是可以和文本串中已匹配成功部分的后缀“AB”相匹配，我们利用这个信息，可以把模式串右移多位，而不仅仅是1位来去继续匹配（换句话说，我们不需要回退文本串的搜索位置），这加快了搜索速率。


同样的，当搜索到下面情况时，文本串中的字符“C”和模式串中的字符“D”不匹配，利用已知的信息，我们右移模式串，不回退搜索位置，继续去查找匹配。


最终，查找成功。


简单来说，文本串和模式串匹配失败时，kmp算法并没有像bf算法描述中一样，将模式串右移1位，从头重新进行搜索，而是利用已匹配信息，不回退文本串的搜索位置，继续将模式串向后移动，减少比较次数，提高了效率。那么当匹配失败时，模式串究竟要向后移动多少位呢？

前缀是指从串首开始到某个位置结束的一个特殊子串。字符串S以i结尾的前缀表示为Prefix(S,i)，也就是Prefix(S,i)=S[0..i]。

真前缀指除了S本身的S的前缀。

后缀是指从某个位置开始到整个串末尾结束的一个特殊子串。字符串S的从i开头的后缀表示为Suffix(S,i)，也就是Suffix(S,i)=S[i..|S|-1]。

真后缀指除了S本身的S的后缀。

回到上文kmp算法匹配流程中，当文本串和模式串匹配失败时，我们右移模式串的位数是多少呢？或者说，当文本串中字符与模式串中字符匹配失败时，应该重新跟模式串中哪个字符再进行匹配呢？