KMP算法的优点就是在于它的高效率，而这种高效率来自于自身串的比较，得出在与母串失配时下一次回溯的位置，从而达到滑动向下比较，从而增大比较的效率；
KMP算法的关键之处就是在于构建next表，这个表是自身与自身的比较结果；
初学者 附代码：
//#include <bits/stdc++.h> #include <iostream> #include <cstring> #include <string> using namespace std; int Next[10000]; void get_next(char b[]) { int i = 0, j = -1; Next[0] = -1;//首先初始化Next[0]=-1 while (b[i] != '\0') { if (j == -1 || b[i] == b[j]) { ++i; ++j; Next[i] = j; } else j = Next[j]; } }//打表结束 //KMP void Index_KMP(char a[], char b[]) { get_next(b); int i = 0,j = 0; int len1 = strlen(a), len2 = strlen(b); while (i < len1&&j < len2)//任意子川或者母串结束都视为比较结束 { if (j == -1 || a[i] == b[j]) { ++i; ++j; } else j = Next[j];//在next表中查找回溯位置 } if (j >= len2) cout << i - len2 + 1 << endl; else cout << "-1" << endl; } int main() { char a[1000], b[1000]; while (cin >> a >> b) { Index_KMP(a, b); } return 0; }