KMP是众多字符串问题的基础

理解next数组尤为重要

next又称前缀数组  

是 它所处位置的前一个位置的元素 与 该链 链首开始 几个元素相匹配(即相同)

 

举个实例来说明：

 

 

next对应的是该位置的前一个元素， 即next[i]对应a[i-1]

因为-1头指针的存在 next均对应前一个 很重要

 

next可以理解为指针，而它指向的位置 就是他的数值对应下标的前一个 

　　即 比如next[7]指向a[ next[7] - 1 ], 也就是a[2]  next[13]指向a[ next[13] - 1 ], 也就是a[5];

结合上一条， 也就是a[6]对应a[2]                           a[12]对应a[5]

 

这样对应的含义是： a[x]与a[y]对应，那么  从链首至a[y]的元素 均能与 a[x]及其之前 相同长度的元素匹配

举个例子 a[12]对应a[5]， 也就是说 a[0]到a[5]这六个元素 能与 a[12]往前(包括a[12])共六个元素匹配  就是 a[0]到a[5] 与 a[7]到a[12] 相同

 

 

这样对应了起来有什么用呢？

这就为查找失败 往前找节约了时间。

 

比如， 我们在第14 这个位置查找失败了， 那么我们只需要回到next[14]这个位置也就是a[7], 看a[7]是否匹配, 若不匹配 再往前回next[7]也就是a[3]的位置

直至查找成功或者回到0

 

为什么呢？

因为next 数组的含义 简单的说 就是 前面有多少匹配 

所以当不匹配了， 只需找到上一个匹配到哪里就可以了。

 

 

实现:

next数组的实现也是用的这个原理

1 void getnext(int len) 2 { 3     int i=0, j=-1; 4     next[0]=-1; 5     while(i

 

 

1 int kmp(int la,int lb) 2 { 3     int i=0, j=0; 4     while(i
     
      =lb)15         return i-lb+1;16     else17         return -1;18 }