已匹配前缀还能留下什么
朴素搜索在部分匹配后失败，会把模式移动到下一个文本起点，从头比较许多刚看过的字符。KMP反而追问：已经匹配部分的后缀，有没有同时也是模式前缀的部分，可以直接继续使用。
例如ababa的末尾aba也是它的开头，说明模式出现重叠时，不必把所有进度清零。预处理记录这类可退回的状态，失配后只丢弃不可能再成立的部分；它利用的是字符关系，而不是猜测文本接下来大概会写什么。
参考：[1]
失配链接与自动机
一种实现为模式位置保存失配链接，失配时沿链接退到较短候选前缀，继续比较当前文本字符。虽然模式状态可能回退，文本位置仍向前推进，避免对原文本整体反复扫描。
另一种实现直接为每个状态和字符准备下一状态，文本每来一个字符就查表转移。Princeton的KMP示例采用这种DFA表；它与只保存失配链接的版本有同一复用思想，但表大小还随字符集范围增加。
线性搜索仍需说明实现与输出
对非空模式，失配表版本可在O(m)时间和空间准备后，用O(n)时间寻找第一处出现；回退的总工作可由前进的匹配进度界定，并非每个字符都各自重做m次比较。完整R字符转移表则通常需要O(Rm)准备空间与时间。
字符编码和返回位置的单位仍由实现规定。寻找全部出现时，还要在每次命中后保留适当重叠状态，而不能简单跳过整段模式。预处理能复用同一模式，但模式改变后旧表也必须更新。