要了解 KMP 算法背后的逻辑，您应该首先了解该 KMP 算法如何优于暴力算法。
Idea
模式发生转变后，朴素算法忘记了有关先前匹配符号的所有信息。因此它有可能一次又一次地将文本符号与不同的模式符号进行重新比较。这导致最坏情况的复杂度为 θ(nm)（n：文本长度，m：图案长度）。
Knuth、Morris 和 Pratt [KMP 77] 的算法利用了先前符号比较所获得的信息。它永远不会重新比较与模式符号匹配的文本符号。因此，Knuth-Morris-Pratt 算法的搜索阶段的复杂度为 O(n)。
然而，为了分析其结构，需要对模式进行预处理。预处理阶段的复杂度为O(m)。由于 m
文字：bacbababaabcbab
图案：abababca
在暴力法中，
将图案逐一滑动到文本上并检查是否匹配。如果找到匹配项，则再次滑动 1 以检查后续匹配项。
void search(char *pat, char *txt)
{
int M = strlen(pat);
int N = strlen(txt);
/* A loop to slide pat[] one by one */
for (int i = 0; i <= N - M; i++)
{
int j;
/* For current index i, check for pattern match */
for (j = 0; j < M; j++)
{
if (txt[i+j] != pat[j])
break;
}
if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
{
printf("Pattern found at index %d \n", i);
}
}
}
上述算法的复杂度为O(nm)。
在上面的算法中我们从未使用过我们处理过的比较数据，
Bacbababaabcbab //let I be iterating variable over this text
Abababca //j be iterating variable over pattern
当 i=0 且 j=0 时，存在不匹配 (text[i+j]!=pat[j])，我们递增 i 直到出现匹配。
当 i =4 时，存在匹配（text[i+j]==pat[j]），递增 j 直到我们发现不匹配（如果 j=patternlength 我们找到模式），在给定的示例中，我们在 j= 处发现不匹配5 当 i=4 时，文本中的 idex 4+5=9 处发生不匹配。匹配的子字符串是 ababa ，
**
Why we need to choose longest proper prefix which is also proper suffix :
**
从上面：我们看到不匹配发生在 9 处，其中模式以子字符串 ababa 结尾。
现在，如果我们想利用迄今为止所做的比较，那么我们可以跳过（增量） i 超过 1，那么比较次数将减少，从而获得更好的时间复杂度。
现在我们可以利用经过处理的比较数据“ababa”获得什么优势。
如果我们仔细看：前缀aba字符串ababa与文本进行比较并匹配，后缀也是如此aba。但‘b’与‘a’不匹配
Bacbababaabcbab
||||||
||||| x
|||| ||
ababab
但根据朴素的方法，我们将 i 增加到 5。但是通过观察我们知道，我们可以将 i = 6 设置为 aba 的下一次出现在 6 处。因此，我们不是与文本中的每个元素进行比较，而是对模式进行预处理用于查找最长的正确前缀，它也是正确的后缀（称为边界）。在上面的“ababa”示例中，最长边框的长度为 3（即aba）。因此增加：子字符串的长度 - 最长边框的长度 -=> 5-3 =2。
如果我们的比较在 aba 处失败，则最长边界的长度为 1 并且 j=3，因此增加 2 。
有关如何预处理的更多信息：http://www-igm.univ-mlv.fr/~lecroq/string/node8.html#SECTION0080 http://www-igm.univ-mlv.fr/~lecroq/string/node8.html#SECTION0080
http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm
