前言

KMP算法可以說說許多學習算法的同學的第一道坎，要么是領會不到KMP算法的思想，要么是知道思想寫不出代碼，網上各種查找。關于算法的書籍上也都有KMP算法的實現，可為啥自己寫不出來呢？博主看得大話數據結構上的分析，書上的代碼都比較精簡，但是不易理解 ，跟著代碼思路走結果也是對的。那么我們為啥我們不可以多寫幾行代碼 更加容易理解呢。博主今天就用普通程序員的思路 去寫KMP算法 采用C語言實現，雖然代碼可能會多那么幾行，如果你能看懂，那我也就很高興了，如果看不懂 請看大話數據結構中KMP的實現領略其思想 然后自己實現代碼沒有必要和書上一模一樣。博主寫的KMP算法是結合之前寫的字符串：BF算法。程序代碼可以循環運行進行測試。

KMP算法介紹

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

KMP算法思路

舉個簡單先說明KMP思想

主串abcdefgab 子串abcdex，我們采用BF算法 當比較到字符x和d時候發現相等，這是主串回溯到字符b 又和 子串abcdex進行比較 然后c...e 和子串abcdex進行比較。我們明顯知道，主串的abcde已經和子串的abcde相等了，而且abcde字符之間互不相等！那么主串中b c 有必要 再次和子串abcd進行比較么，沒有必要，因為 主串abcde和子串abcde匹配 而且他們 之間又是互不相等 所以沒有 b...e和子串進行比較了。只需要步驟①和步驟⑥ 請看下圖（大話數據結構上的圖）

如果在不相等的字符前面有重復的字符串的情況怎樣呢？主串abcabcabc和子串abcabx 是不是應該和下圖一樣呢？仔細想一想是不是呢，領悟...，子串回溯到不相等字符前 的 重復字符串的后面。

所以我們回溯的重點是子串而不是主串，尤其是當我們子串有大量不重復字符且長度越長，節省的比較次數越多。

KMP算法和BF算法和核心區別就是遇到不相等的字符串 主串和子串的回溯問題，BF算法遇到不相等字符主串回溯到之前開頭比較的第一位字符的下一位 子串回溯到第一位 會進行大量沒有必要的比較，而KMP算法會根據子串中字符情況進行比較。

next 數組推導

下面我們就進行子串中每個字符回溯位置的推導，將子串每個字符回溯的位置放在一個next數組中，字符串格式采用書上推薦的格式sub_str[0]存放子串長度，sub_str[1]開始放字符，那么我們的next數組同樣也是從[1]開始放字符對應的回溯位置。比如說我們匹配的子串是ababaaaba，每個字符的next值就是他前綴表達式和后綴表達式相等元素個數+1。

子串下標123456789 123456789

子串ababaaaba aaaaaaaab

next值 ? ? 011234223 012345678

注意 next[1] = 0 next[2] = 1 這是不變的，然后從第3位字符開始，我們就要進行前綴后綴字符重復的計算了，重復1位next[]值是2重復2位next[]值是3 依次類推，當比較到不等字符時 最后一位和第一位重新比較如果還是不等那next值就是1，否則就是2。總感覺描述代碼實現不清楚，下面還是看代碼吧。

?

/* 獲取子串的next數組 沒有優化的的next數組 */ int* NextKMP1(uchar* sub_str) {int subLen = sub_str[0];int* next = (int*)malloc(sizeof(int)*(subLen + 1));next[1] = 0;//特殊情況 子串只有一個字符if (subLen == 1){return next;}next[2] = 1;int start = 1;int end = 2;int count = 1;for (size_t i = 3; i <subLen + 1; i++){//i 當前字符的下標，計算它的next值if (sub_str[start] == sub_str[end]){next[i] = ++count;start++;end++;}else{//遇到不相等，那就只能從頭開始比較咯，start = 1;count = 1;if (sub_str[start] == sub_str[end]){next[i] = ++count;//相等前綴往后走start++;}else{next[i] = 1;//不相等 start停留在第一個位置}//后綴一直往后走end++;}}return next; }

next 數組優化

后來前輩們發現KMP還是有缺陷的，比如我們的主串aaaabcde和子串aaaaax，按照KMP算法next值分別為012345，按照KMP算法比較如下：

其中二、三、四、五是多余的判斷，因為其位置上的字符都和首字符'a'相等，那么可以用首位next[1]的值進行取代當前next[]的值。下面請看代碼，就加了2行語句。

/* 獲取子串的next數組 優化后的next數組 */ int* NextKMP2(uchar* sub_str) {int subLen = sub_str[0];int* next = (int*)malloc(sizeof(int)*(subLen + 1));next[1] = 0;//特殊情況 子串只有一個字符if (subLen == 1){return next;}next[2] = 1;int start = 1;int end = 2;int count = 1;for (size_t i = 3; i <subLen +1; i++){//i 當前字符的下標，計算它的next值if (sub_str[start] == sub_str[end]){next[i] = ++count;start++;end++;}else{//遇到不相等，那就只能從頭開始比較咯，start = 1;count = 1;if (sub_str[start] == sub_str[end]){next[i] = ++count;//相等前綴往后走start++;}else{next[i] = 1;//不相等 start停留在第一個位置}//后綴一直往后走end++;}//優化 如果start指向的字符和當前字符相等，那么就取前綴相同字符的next值if (sub_str[start] == sub_str[end]){next[i] = next[start];}}return next; }

完整代碼

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <string.h> typedef unsigned char uchar; /* 獲取子串的next數組 優化后的next數組 */ int* NextKMP2(uchar* sub_str) {int subLen = sub_str[0];int* next = (int*)malloc(sizeof(int)*(subLen + 1));next[1] = 0;//特殊情況 子串只有一個字符if (subLen == 1){return next;}next[2] = 1;int start = 1;int end = 2;int count = 1;for (size_t i = 3; i <subLen +1; i++){//i 當前字符的下標，計算它的next值if (sub_str[start] == sub_str[end]){next[i] = ++count;start++;end++;}else{//遇到不相等，那就只能從頭開始比較咯，start = 1;count = 1;if (sub_str[start] == sub_str[end]){next[i] = ++count;//相等前綴往后走start++;}else{next[i] = 1;//不相等 start停留在第一個位置}//后綴一直往后走end++;}//優化 如果start指向的字符和當前字符相等，那么就取前綴相同字符的next值if (sub_str[start] == sub_str[end]){next[i] = next[start];}}return next; }/* 獲取子串的next數組 沒有優化的的next數組 */ int* NextKMP1(uchar* sub_str) {int subLen = sub_str[0];int* next = (int*)malloc(sizeof(int)*(subLen + 1));next[1] = 0;//特殊情況 子串只有一個字符if (subLen == 1){return next;}next[2] = 1;int start = 1;int end = 2;int count = 1;for (size_t i = 3; i <subLen + 1; i++){//i 當前字符的下標，計算它的next值if (sub_str[start] == sub_str[end]){next[i] = ++count;start++;end++;}else{//遇到不相等，那就只能從頭開始比較咯，start = 1;count = 1;if (sub_str[start] == sub_str[end]){next[i] = ++count;//相等前綴往后走start++;}else{next[i] = 1;//不相等 start停留在第一個位置}//后綴一直往后走end++;}}return next; }/* 用KMP算法查詢子串在主串中的位置 dest_str:目標字符串 sub_str:子串 next:子串的next數組 begin:開始查詢的位置 return 返回子串在主串中的index */ int IndexKMP(uchar* dest_str,uchar* sub_str,int* next,int begin) {int subLen = sub_str[0];uchar* dest = dest_str + 1 + begin;uchar* sub = sub_str + 1;int count = 0;//和暴風算法一樣while (*dest != 0){count++;//判斷第一個字符是否相等，不相等 主串往后移if (*dest != *sub){dest++;continue;}//碰到相等字符，記錄比較起始位置uchar* temp = dest;//走到這里主串和子串第一個字符相等，繼續往下進行比較sub++;dest++;while (*sub !=0){ count++;//相等繼續比較后面的字符if (*dest == *sub){dest++;sub++;}else{//遇到不相等的字符 就回溯//BF算法就是從頭再來了，主串回溯到標記的下一位繼續和子串的第一位開始進行比較//dest = temp + 1;//sub = sub_str + 1;//KMP 算法，就是比較字符不等時，next[]有值，主串不進行回溯，把子串進行回溯！這是KMP的核心思想。if (next[sub - sub_str] == 0)//next[]值為0主串比較下一位{dest = temp + 1;sub = sub_str + 1;}else{//sub = sub_str + 1 + next[sub - (sub_str + 1) + 1] - 1;sub = sub_str + next[sub - sub_str];//別寫錯了喲，這里是關鍵。}break;}}//子串遍歷完畢，說明子串在主串中匹配完畢if (*sub == 0){printf("KMP算法字符比較的次數:%d\n", count);return dest - (dest_str + 1) - subLen;}}printf("沒有找到\n");return -1; } /* 將普通字符串轉換為KMP需要的字符串格式 char* src = "abc";--> char* dest = {3,'a','b','c','\0'}; */ uchar* StrConvert(char* src) {int len = strlen(src);if (NULL == src || len == 0 ){return NULL;}int newLen = len + 2;//\0 占一個位置，字符數量占一個位置uchar* str = malloc(sizeof(char)*newLen);memset(str, 0, newLen);str[0] = len;//為了是主串可以更長使用unsigned char ，所以主串最長不要超過255個字符strncpy(str + 1, src, len);return str; } /* 用BF算法查詢子串在主串中的位置 dest:目標字符串 sub:查詢子串 begin:開始查找的下標 return 返回子串在主串中的index */ int StrIndexBF(char* dest_str, char* sub_str, int begin) {if (begin < 0){begin = 0;}char* dest = dest_str + begin;char* sub = sub_str;int count = 0;//記錄比較次數//通過字符一個一個進行比較while (*dest != 0){count++;//和子串第一個字符不相等if (*dest != *sub){dest++;continue;}char* temp = dest;//走到這里主串和子串第一個字符相等，繼續往下進行比較sub++;dest++;//遇到不相等的字符就回溯，主串回溯到標記的下一位繼續和子串的第一位開始進行比較while (*sub != 0){count++;if (*sub == *dest){sub++;dest++;}else{sub = sub_str;dest = temp + 1;break;}}//判斷子串是否遍歷完畢,返回位置if (*sub == 0){printf("BF算法字符比較的次數:%d\n", count);return dest - dest_str - strlen(sub_str);}}printf("沒有找到\n");return -1; }/* 打印next數組的數據 */ PrintNext(int* arr,int length) {//next[0]為空閑空間for (size_t i = 1; i < length; i++){printf("%d ", arr[i]);}printf("\n");return 0; }/* KMP算法查找子串 dest 目標字符串 sub 查詢子串 begin 開始查找的下標 */ int StrIndexKMP(char* dest,char* sub,int begin) {if (NULL == dest || NULL == sub || begin < 0){printf("傳入參數有誤...\n");return -1;}uchar* dest_ = StrConvert(dest);uchar* sub_ = StrConvert(sub);int* nextArr1 = NextKMP1(sub_);int* nextArr2 = NextKMP2(sub_);printf("KMP的 next :");PrintNext(nextArr1, sub_[0]+1);printf("KMP的 nextval:");PrintNext(nextArr2, sub_[0] + 1);return IndexKMP(dest_,sub_, nextArr2,begin); }int main(int argc, char *argv[]) {char dest[256] = { 0 }, sub[256] = { 0 }, num[5] = { 0 };int begin = 0;while (1){memset(dest, 0, 256);memset(sub, 0, 256);memset(num, 0, 5);printf("請輸入目標字符串(#退出):");fgets(dest, 256, stdin);dest[strlen(dest) - 1] = 0;//去掉換行符if (strcmp(dest, "#") == 0){break;}printf("請輸入查詢起始位置(不輸入從0開始):");fgets(num, 5, stdin);if (strlen(num) != 1){num[strlen(num) - 1] = 0;//去掉換行符sscanf(num, "%d", &begin);}printf("請輸入查詢子串:");fgets(sub, 256, stdin);sub[strlen(sub) - 1] = 0;//去掉換行符int index = StrIndexBF(dest, sub, begin);printf("BF:dest=%s,sub=%s,begin=%d,index=%d\n", dest, sub, begin, index);index = StrIndexKMP(dest, sub, begin);printf("KMP:dest=%s,sub=%s,begin=%d,index=%d\n", dest, sub, begin, index);}return 0; }

運行結果檢測

我們主要看next數組值和優化后的nextval數組值是否推導正確，這是KMP算法的關鍵，如果你能寫BF算法然后能將next數組用代碼推算出來，那么你的KMP算法就ok了，然后可能就是一些細節的上的完善了。

總結

以上是生活随笔為你收集整理的字符串：你看的懂的KMP算法（带验证）的全部內容，希望文章能夠幫你解決所遇到的問題。

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