写在前面：
我将KMP算法分为了三个篇章：
【原理篇】：主要讲解KMP实现的原理，以及手动求NEXT数组。
【数理篇】：主要讲解如何在手动求出NEXT数组的情况下，找出数学规律，为之后的算法实现奠定基础。
->【实现篇】：主要讲解以C语言代码的方式实现KMP算法，以及NEXT数组的优化。
本篇章将结合前两章所讲内容，代入C代码进行实现吗。可点访问我的个人主页进行回顾，也可点击上方对应链接访问，那么我们开始了。
🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈
C代码实现：
初始化与基础情况处理：
int KMP(char *str,char*pat,int pos) { assert(str&&pat); const int lenstr=strlen(str); const int lenpat=strlen(pat); int *next=NULL; next=(int*)malloc(sizeof(int)*lenpat); if(!lenstr||!lenpat)return -1; if(pos<0||pos>=lenstr)return -1;
定义一个函数，传入参数为两个字符串，以及一个pos（表示从主串str的哪个位置开始搜寻子串pat）
若传入参数为空则assert报警。将主串与模板串的长度存入变量，防止以后每次想要获取长度时都调用函数，节省时间。
创建NEXT数组分配长度为LENPAT的空间大小。若主串||模板串大小为0||pos<0||pos>=主串长度，则函数结束。
NEXT数组实现：
PAT[i]=PAT[k]
在PAT[i]=PAT[k]的情况下，NEXT[i+1]=k+1。因为NEXT数组0号位与1号位是规定好的-1与0的值，所以我们初始化时直接将他们填入即可，此时我们的i从2号位开始而我们的k从0号位开始，此时的情况如下方所示。
k |
实际的i | i（要求的） | |||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| PAT字符串 | a | b | a | a | b | a | b | c | a | b | c |
| NEXT数组 | -1 | 0 |
套用我们的公式，可以很轻松的得出NEXT[2]=1(k+1)。但是，在代码当中这个i所对应的NEXT数组，也就是NEXT[i]是未知的，而我们之前所有的推论都基于NEXT[i]=k，也就是NEXT已知的情况下，所以公式里的i实际上是这里的i-1。所以真正的（代码）公式是NEXT[i+1]=k+1
k |
实际的i | i+1 | |||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| PAT字符串 | a | b | a | a | b | a | b | c | a | b | c |
| NEXT数组 | -1 | 0 |
所以这时的NEXT[i+1]=-1+1=0;
PAT[i]!=PAT[k]
综上这里写的i也是代表我们要求的i，所以我们现在实际要判断的是i-1的位置上PAT[i-1]!=PAT[k]，此时k=NEXT[k]进行一个回滚的操作。
NEXT数组代码实现：
void GetNext(char*pat,int * next,int lenpat) { next[0]=-1; next[1]=0; int i=2;//当前i下标 int k=0;//next数组里的数 for(;i<lenpat;) { // p[i]==p[k] next[i+1]=k+1 if(k==-1||pat[i-1]==pat[k]) { next[i]=k+1; i++; k++; } else { k=next[k]; } } }
首先进行初始化。之后进入一个循环，若满足k==-1（边界的设置）||pat[i-1]==pat[k]则说明匹配成功，两个下标加一，进入到下一个匹配，反之k=NEXT[k]进行一个回滚的操作。
至此NEXT数组函数完结。
KMP函数：
int KMP(char *str,char*pat,int pos) { assert(str&&pat); const int lenstr=strlen(str); const int lenpat=strlen(pat); int *next=NULL; next=(int*)malloc(sizeof(int)*lenpat); if(!lenstr||!lenpat)return -1; if(pos<0||pos>=lenstr)return -1; GetNext(pat,next,lenpat); int i=pos; int j=0; while(i<lenstr&&j<lenpat) { if(j==-1||str[i]==pat[j]){ i++; j++; } else { j=next[j]; } } if(j>=lenpat)return i-j; return -1; }
求出NEXT数组后，返回到KMP函数当中，进入主串与模板串的匹配。循环条件为两个指针小于各自数组的长度。当j==-1||str[i]==pat[j]，表示匹配上了，此时指针前移，其余部分与NEXT数组实现大同小异，这里就不过多赘述。
之后返回i-j表示从主串当中哪里开始匹配上的。否则返回-1.
KMP算法代码部分：
#include<stdio.h> #include<string.h> #include<assert.h> #include<malloc.h> // str为主串 pat为子串 pos为寻找的起始位置 void GetNext(char*pat,int * next,int lenpat) { next[0]=-1; next[1]=0; int i=2;//当前i下标 int k=0;//next数组里的数 for(;i<lenpat;) { // p[i]==p[k] next[i+1]=k+1 if(k==-1||pat[i-1]==pat[k]) { next[i]=k+1; i++; k++; } else { k=next[k]; } } } int KMP(char *str,char*pat,int pos) { assert(str&&pat); const int lenstr=strlen(str); const int lenpat=strlen(pat); int *next=NULL; next=(int*)malloc(sizeof(int)*lenpat); if(!lenstr||!lenpat)return -1; if(pos<0||pos>=lenstr)return -1; GetNext(pat,next,lenpat); int i=pos; int j=0; while(i<lenstr&&j<lenpat) { if(j==-1||str[i]==pat[j]){ i++; j++; } else { j=next[j]; } } if(j>=lenpat)return i-j; return -1; } int main() { printf("%d\n",KMP((char*)"ababcabcdabcde", (char*)"abcd",0)); } // 有一种植物有一种动物像鸡 请问是什么植物和动物
完结撒花：
留有一个彩蛋看上方最后一行的注释（doge
附上Gitee链接，若想要完整代码可以自取KMP算法实现。
至此，本篇博客的内容九分钟带你弄懂KMP算法【实现篇】告一段落，KMP相关的所有内容也已更新完毕，可访问我的主页。进行查看，接下来我会更新LeetCode上KMP相关的算法题。
若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。
若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。
诸君，山顶见！
🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈
