目录
本篇文章参考王道数据结构内容，详细引导KMP算法的内容 ，建议先看一下字符串的存储结构(1条消息) 串的存储结构 --王道_莫浅子的博客-CSDN博客
朴素模式匹配算法
什么是模式匹配
串的模式匹配就是在子串中找到与模式串相同的子串，并返回其所在位置。
int idex(SString S,SString T){
int k = 1;
int i = k, j = 1;
while(i <= S.length && j <= T.length)
{
if(S.ch[i] == T.ch[j])
{
i++;
j++; //继续比较后面字符
}
else{
k++; //检查下一个子串
i = k;
j = 1;
}
if(j > T.length)
return k;
else
return 0;
}
} 为什么会出现return 0的情况，假设T为a o o,那么会出现 i 大于串的长度 ，而 j 没有超出串的长度，则跳出循环，匹配失败
朴素算法算法性能分析：
若模式串长度为m，主串长度为n，则
匹配成功的最好时间复杂度：O(m)
匹配失败的最好时间复杂度：O(n-m+1)=)(n-m)约等于O(n)
如果出现一下情况
最坏的时间复杂度是O(mn）
KMP算法
举个例子如下图，子串是google，主串是googlogooglegoolo
我们看看当我进行完前面的操作后，是否需要继续重i = 2， j = 1开始看起呢
看下面的例子
当我们发现j = 6的时候我们知道了 i 现在所指向一定不等于 e ,由于前面我们进行判断过，所以我们知道了i 不需要从 6 - 10开始匹配看，因为前面我们看过了我们不用回溯，况与 j = 1的时候比较就行。
移动之后，如果该字直接可以让i = 11的情符是 g 那么让那么i++ , j++ 。如果该字符不是 g ,那么让·i++ ，j = 1 。4
如下图
第二种情况看下面例子
如果前面几个都进行了匹配但是突然发现当 j = 5的时候与i = 9的地方不匹配，那么回溯的时候，由于前面几个进行了匹配，i 不用回到 6，7的位置，当 i 到8的位置是可以的，因为我们只能确定 i= 9的位置不等于 I ，但是我们不确定是不是 o ,所以我们可以把 i 移到 8的位置，而 j 移到 8的位置，总的来说，就是如果 j = 5发生不匹配，那么 j 回到 2，而 i 到 8。
第三种情况看下面的例子
当 j = 4与i = 6，发生了不匹配 ，i = 4与 i = 5情况由于都是 o,一定不和 g 匹配，所以跳过，应该从i = 6 开始（但是实际上，i = 6 与 g 匹配过肯定不等于 g，这个情况先不考虑）
若 j = 4 的时候发生不匹配，应该让 j = 1,i = 6 。
第四种看下面的例子
如果 i = 5的时候，与 j = 3的时候不匹配，同样的只能确定 i = 5的位置不等于o,不能确定是否等于g ，所以如果 j = 3的时候，j 退到 j = 1,而 i 的位置不变
最后一种情况
如果 j = 2的时候与 i = 4的时候不匹配，那么我们让 j = 1,i = 4。
汇总一下
我们把这些情况放到表格中去
这个表格叫next[7]
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 1 | 1 | 1 | 2 | 1 |
当 j = k ，且发现字符不匹配的时候，令 j = next[k] 来用
| g | o | o | g | l | e |
| 1 | 2 | 3 | 4 | 5 | 6 |
代码
int Index_KMP(SString S,SString T,int next[]){
int i = 1, j = 1;
while(i <= S.length && j <= T.length){
if(j == 0 || S.ch[i] == T.ch[i]){
++i;
++j; //继续比较后继字符
}
else{
j = next[j]; //模式串向右移
}
if(j > T.length){ //匹配成功
return i - T.lenght;
}
else
return 0;
}
}注意：
1、j = 0 的情况是由于当 j = 1的时候 next [ j ]等于0，然后 j ++，变成 j = 1,i ++ 。
2、这里面 ++ j 与 ++ i 和 j ++ 与 i ++ 效果是一样的
求模式串的next数组
看下面的例子
当 j = 6匹配失败的时候，它的next[ 6 ] = 3
在看这个情况
当 i = 7匹配失败的时候 ，让 j 指向 j = 5 的位置，所以它的next[7] = 5
在看这个例子
当 j = 5 匹配失败的时候，把字符往右移一格
同样的也可以匹配到，我们让next [5] = 4 。虽然继续往后移主串与模式串仍能匹配，我们应该选择匹配长度最大的
继续看下一种情况
当 j = 5 不匹配的时候我们应该让 next [ j ] = 1
最后在看这个例子(为什么next[1] = 0)
当 j = 1,就匹配失败的时候 我们可以让 j 设置为 0，然后 j 与 i 同时 ++
即对于任何串都可以让 next [ 1 ] = 0
总结：求模式串的next数组
如果你没看懂上面的操作，没关系，只要知道如下操作就行
串的前缀：包含第一个字符，且不包含最后一个字符的子串.
串的后缀：包含最后一个字符，且不包含第一个字符的子串.
当第 j 个字符匹配失败，由前 1 -- j - 1个字符组成的串记为S，则：next [j] = S的最长相等的前后缀长度+ 1 。
特别 next[1] = 0;
下面通过一个列子来看
当模式串为 'a b a b a a'
| 序号 j | 1 | 2 | 3 | 4 | 5 | 6 |
| 模式串 | a | b | a | b | a | a |
| next [j] | 0 | 1 | 1 | 2 | 3 | 4 |
j 为1的时候无可置疑的选择next[ 1 ] = 0,
j 为2的时候ab相等前缀和后缀长度都为 0 ，next [ 2 ] = 1 (0+1)
j 为3的时候aba，前缀为a，后缀为b，不相等，next [ 3 ] = 1 ( 0+1)
j 为4的时候abab，前缀为a,后缀为a的时候最长相等子串，next [4] = 2 (1+1)
j 为5的时候ababa ，当前缀为ab，后缀为ab的时候为最长相等子串，next [5] = 3 ( 2+ 1)
j 为6的时候ababaa,当前缀为aba，后缀为aba的时候为最长相等子串，next [6]= 4 (3+ 1)
求模式串T的next数组
void get_next(SString T,int next[])
{
int i = 1,j = 0;
next[1] = 0;
while(i < T.length){
if(j ==0 || T.ch[i] == ch[j] )
{
++i;
++j;
next[i] = j;
}
else
j = next[j];
}
}上面的参考，其实也可以这样写
void get_next(String T)
{
int i = 1,j = 0;
next[1] = 0;
while(i < T.length){
if(j ==0 || T.ch[i] == ch[j] )
{
next[++i] = ++j;
}
else
j = next[j];
}
}KMP算法
int Index KMP(SSTring S,SString T){
int i = 1,j = 1;
int next[T.length+1];
get_next(T,next);
while(i<=S.length&&j<=T.length){
if(j==0 || S.ch[i] == T.ch[j]){
++i;
++j;
}
else
j = next[j];
}
if(j> T.length)
return i - T.length;
else
return 0;
} 
KMP算法优化
根据上面我们发现有这个情况，就是我们知道 i 指向 4 的位置 不等于g，但是我们仍有 next [ 4 ] = 1 ,继续比较了g，有点重复，所以我们可以作出优化，让next[ 4 ] = 0，j = 0 。 这样 j++,i++,让 j = 1 ， 与 i = 5 进行比较了。
nextval数组的求法
先算出next数组
先令nextva[ 1 ] = 0
for (int j = 2; j <= T.lenght; j++){
if(T.ch[next[ j ] == T.ch[j)
nextval[ j ] = nextval [next [ j ] ];
else
nextval [ j ] = next[ j ];
] }