通俗的来说就是在需要匹配的那个串上给每个位置一个失配指针\(fail[j]\)，表示在当前位置\(j\)失配的时候需要返回到\(fail[j]\)位置继续匹配，而这就是\(KMP\)算法优秀复杂度的核心。
实现失配数组的匹配就是把需要查找的那个字符串进行一遍前缀和后缀之间的匹配。我们举个例子"ababa"这里真前缀分别为"a","ab","aba","abab"，真后缀为"a","ba","aba","baba",找到他们的最大相同位置，就是\(fail\)指针，
我们设\(kmp[i]\) 用于记录当匹配到模式串的第 \(i\) 位之后失配,该跳转到模式串的哪个位置，那么对于模式串的第一位和第二位而言，只能回跳到 \(1\)，因为是 \(KMP\)是要将真前缀跳跃到与它相同的真后缀上去（通常也可以反着理解），所以当 \(i=0\) 或者 \(i=1\) 时,相同的真前缀只会是 \(str1(0)\)这一个字符，所以\(kmp[0]=kmp[1]=1\)。
模板+代码KMP字符串匹配
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6+10; char a[maxn],b[maxn]; int kmp[maxn]; int main(){ cin>>a+1>>b+1; int lena = strlen(a+1); int lenb = strlen(b+1); int j = 0; for(int i=2;i<=lenb;++i){//自己跟自己匹配处理出kmp数组 while(j && b[i] != b[j+1]){ j = kmp[j]; } if(b[i] == b[j+1])j++; kmp[i] = j; } j = 0; for(int i=1;i<=lena;++i){ while(j && a[i] != b[j+1]){ j = kmp[j]; } if(a[i] == b[j+1])j++; if(j == lenb){//匹配完了就输出位置 printf("%d\n",i-lenb+1); j = kmp[j];//返回失配位置 } } for(int i=1;i<=lenb;++i){ printf("%d ",kmp[i]); } return 0; }