一，解决问题
kmp算法解决的是字符串匹配的问题，具体来说假定我们要在主串s[ ] 中匹配模式串p[ ]，找到匹配到的位置loc；
二，具体实现和演变过程
最自然的想法是暴力写法 （BF）枚举主串字符s[ i ] ,和模式串p[ j ]。一个一个匹配，如果匹配失败，i指针回退回起点，往前进一位，再次进行比较，知道匹配成功。
代码如下：
#include#define int long longconst int INF = 1e18 + 10,maxn = 1e5 + 10;using namespace std;char p[maxn],s[maxn];int n,m;signed main (){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>m>>(p + 1)>>n>>(s + 1); for(int i = 1; i <= n; i++){ int j = 1; while(s[i] == p[j] && j <= m){ i++; j++; } if(j == m + 1) { cout<< i - j + 1 << '\n'; } i = i - j + 1;//回退 } return 0;}
时间复杂度是O(nm) 因为对于s[i]，最多被比较m次，每次比较都会++指针，共有n个字符会被比较。
kmp算法就是通过一些方法减少了比较次数，减少了时间复杂度的做法。
具体来说，我们先想办法使得i指针不回退，首先，我们已经知道匹配失败的位置前面所有位置都是匹配成功的，假设匹配失败的前一个位置为j 那么匹配失败的位置为j + 1，因为j + 1匹配失败，那么我们需要向右滑动字符串p，此时假设有一个ne【】数组，记录了p[i] 使得 p[1,ne[j]] = p[j-ne[j]+1,j] 的值即最长相等真字串长度，那么由于p[1,j] 之前是匹配成功的，那么只需要将j 回退到p[1,ne[j]] = p[j-ne[j]+1,j] 即可，任然只需要比较p[j + 1] = s[i]。代码如下：
for(int i = 1,j = 0; i <= m; i++){ while(j && p[j + 1] != s[i]) j = ne[j]; if(p[j + 1] == s[i]) j++; if(j == n){ cout<<i - n<<' '; j = ne[j]; } }
那么问题来了，如何确定ne【】数组，我们采取相同的策略，假定现在匹配前缀p[1,j] 和后缀 p[i- j + 1,i]如果匹配成功，只需将长度j++，（还记得ne【】数组的定义吗）如果匹配失败，只需要前后缀各自减少长度ne[j] 同理，现在匹配失败的位置是p[j + 1],那么只需回退j指针就能找到前一个p[1,j – ne[j]] 和 p[i-ne[j]+1,i] (更新位置i时。i前面的ne数组已经确定)那么代码如下（j 表示的意义不仅是匹配位置，也有长度的意思，以为前缀表示为p[1,j]）：
//ne数组的生成过程中，考察ne[i]和ne[i-1] i >= 2; //完成ne[i-1]匹配后可以确定p[1,j] = p[i-j,i-1] //那么如果p[i] != p[j+1] //应该回退j舍弃部分p[1,j] 的后缀和 p[i-j,i-1] 的前缀 //回退到j = ne[j] (i-1前的ne数组都已完成维护) //此时p[1,ne[j]] 是p[1,j] 的真子集并且p[1,ne[j]] = p[j-ne[j]+1,j] //匹配过程 for(int i = 2, j = 0; i <= n; i++){ while(j && p[i] != p[j + 1]) j = ne[j]; if(p[i] == p[j + 1]) j++; ne[i] = j; }
那么完整的代码如下：
#include#define int long longconst int INF = 1e18 + 10,maxn = 1e6 + 10;using namespace std;char p[maxn],s[maxn];int ne[maxn];signed main (){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int n,m; cin>>n>>(p+1)>>m>>(s+1); //ne数组的生成过程中，考察ne[i]和ne[i-1] i >= 2; //完成ne[i-1]匹配后可以确定p[1,j] = p[i-j,i-1] //那么如果p[i] != p[j+1] //应该回退j舍弃部分p[1,j] 的后缀和 p[i-j,i-1] 的前缀 //回退到j = ne[j] (i-1前的ne数组都已完成维护) //此时p[1,ne[j]] 是p[1,j] 的真子集并且p[1,ne[j]] = p[j-ne[j]+1,j] //匹配过程 for(int i = 2, j = 0; i <= n; i++){ while(j && p[i] != p[j + 1]) j = ne[j]; if(p[i] == p[j + 1]) j++; ne[i] = j; } for(int i = 1,j = 0; i <= m; i++){ while(j && p[j + 1] != s[i]) j = ne[j]; if(p[j + 1] == s[i]) j++; if(j == n){ cout<<i - n<<' '; j = ne[j]; } } return 0;}