百度百科：KMP算法是一種改進的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人們稱它為克努特—莫里斯—普拉特操作（簡稱KMP算法）。KMP算法的核心是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數以達到快速匹配的目的。具體實現就是通過一個next()函數實現，函數本身包含了模式串的局部匹配信息。KMP算法的時間復雜度O(m+n)。

?上圖中我們眼睛可以看出來k的位置? 但是在程序中實現呢 ？

通常就是弄個next數組來存放應該j應該回退的位置k? 這個數組怎么求才是這個KMP算法的核心所在！

?數學推導過程看這個就好? 他講的就是next[1] = 0? 子串開頭下標從1開始的：

一定要看這個? 講的超級好！！！！！！！！！！！！！！！！！！！！！！
KMP算法之求next數組代碼講解_嗶哩嗶哩_bilibili本視頻旨在解決KMP算法中如何用代碼求解next數組的問題，并對其中的實現代碼進行了逐行推演解釋，由于up主知識水平有限，如果其中有不足的地方希望大家多多諒解~O(∩_∩)O~~https://www.bilibili.com/video/BV16X4y137qw?from=search&seid=7521948390163041197&spm_id_from=333.337.0.0

next數組所求代碼：

int *Get_next(const char *sub)
{//assertint len_sub = strlen(sub);int *next = (int*)malloc(sizeof(int) * len_sub);assert(next != 0);next[0] = -1;next[1] = 0;int j = 1;int k = 0;//通過已知推位置  j是已知  則j+1是未知     while(j+1 < len_sub)//未知位置需要合法  所以做了一個判斷{if(sub[j] == sub[k] || (k==-1))//要么相等k++賦值，要么不相等k一直回退，觸發了保底機制（k==-1）{//next[++j] = ++k;k++;j++;next[j] = k;}else{k = next[k];}}return next;
}

KMP_search的代碼：

int KMP_Search(const char *str, const char *sub, int pos)//pos代表主串開始查找的下標位置
{assert(str!=NULL && sub!=NULL);if(pos<0 || pos>=(int)strlen(str)){//return -1;pos = 0;}int len_str = strlen(str);//主串的長度信息int len_sub = strlen(sub);//子串的長度信息int i = pos;//主串開始位置int j = 0;//子串開始位置int *next = Get_next(sub);while(i<len_str && j<len_sub){if((j==-1) || str[i] == sub[j])//如果相等，兩者同時向后走，i++,j++{i++;j++;}else{//i不回退j = next[j];//next[j] == k}}//此時while循環退出   兩種情況，要么i走出范圍   要么j走出范圍if(j >= len_sub)//如果子串的j走出范圍，找到了，返回i-j{return i-j;}else//否則沒有找到，匹配失敗，返回-1{return -1;}
}

KMP算法最難理解的就是next數組的數學推導? 剩下的和BF算法基本一毛一樣！

“錢可以解決你百分之九十九的不開心，啊？你問還有百分之一的不開心呢 那是不夠有錢！”

總結

以上是生活随笔為你收集整理的BF算法优化-------KMP算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。