第一种形式（数据结构严蔚敏版）
（字符串下标均从1开始）
先上代码：
#include <iostream>#include <cstdio>#include <vector>using namespace std;int Next[100];char S[100],T[100];vector<int> ans;int main(){ int n,m; cin>>n>>m; cin>>S+1>>T+1; //求Next数组 int i = 1,j = 0; Next[1] = 0; while(i<=m) { if(j==0 || T[i] == T[j]) { ++i,++j; Next[i] = j; } else j = Next[j]; } /* for(int i = 1 ; i<=m ; i++) cout<<Next[i]<<" "; cout<<endl; */ //主串与模式串开始匹配 cout<<endl; i = 1,j = 1; while(i<=n) { if(j==0 || T[j] == S[i] && i+1<=n) { ++i,++j; } else j = Next[j]; if(j==m) { ans.push_back(i-m+1); j = Next[j]; } } int k = 0; while(k<ans.size()) { cout<<ans[k++]<<" "; } return 0;}思路
在该程序中，主串的 i 与 j 同时从1开始遍历，j 等于 0 的情况表示需要模板串从头开始与主串匹配，j 不等于 0 时则 i 与 j 同时遍历并判断能否匹配，若失配，i 固定不回溯，模板串向前移动（ j = Next[ j ];）重复此过程，当 j 等于 模板串的长度时，说明在主串中存在此模板串，记录位置，模板串继续移动（ j = Next[ j ]; ) ，继续匹配。
第二种形式
上代码：
#include <iostream>using namespace std;const int N = 10010,M = 100010;//p为模板串，s为主串int n,m;char p[N],s[M];int Next[N];int main(){ cin>>n>>p+1>>m>>s+1; Next[1] = 0; for(int i = 2,j = 0; i<=n ; i++) { while(j && p[i] != p[j+1]) j = Next[j]; if(p[i] == p[j+1]) ++j; Next[i] = j; } /* for(int i = 1;i<=n;i++) cout<<Next[i]<<" "; cout<<endl; */ for(int i = 1,j = 0; i<=m ; i++) { while(j && s[i]!=p[j+1]) j = Next[j]; if(s[i] == p[j+1]) ++j; if(j == n) { cout<<i-n<<" "; j = Next[j]; } } return 0;}思路
此代码与第一种形式的区别就在于求Next数组上，第一种是忽略当前位置，再当前位置前的串中求最长相同前缀后缀，将此长度+1并记录到Next数组中，由于在第一个代码中，i 与 j 都是从1开始遍历，当 j = Next[ j ] 后，直接将 i 与 j比照，而第二种形式种，求Next数组时，是观察包括当前位置的串种最长的相同前缀后缀，并直接记录在Next数组种，由于第二种代码中，i 从1开始，j 从0开始，每次比照的是 i 与 j + 1；所以当在匹配过程中发生失配时，j = Next[ j ] 实际是当前位置（i 或者 j+1）的前一个位置的最长相同前缀后缀，j + 1 后 与 i 比照，实际上与第一种形式相同，但我认为这是两种不同的记录方式。
看完KMP算法，真的是敬佩三位科学家，另外，在学习过程中也遇到了很多困难，目前，对该算法的了解也只是很片面，通俗，继续努力！！！
