前言

KMP算法最近看了很多的博客和視頻始終沒有清楚理解NEXT數組的構建，在B站看到正月點燈籠大神的視頻，里面提出的前綴表對我有很大啟發，今天來記錄分享一下。
BILIBILI 正月點燈籠

定義

string text;//目標字符串 string pattern; //匹配字符串 int i,j;//為兩個字符串索引 text[i],pattern[j] int n,m;//分別為兩個字符串長度

算法

KMP框架

在燈神的視頻里引入了一個前綴表（Prefix table）的概念來替代Next數組，我覺得更容易理解，在這里前綴的意思我就不贅述了，可以自行百度。
假設待匹配的字符串Pattern=“ABABAAC”。

0 A0 AB1 ABA2 ABAB3 ABABA1 ABABAA0 ABABAAC

于是我們可以根據每一個字母的前綴數建立一個前綴表，為了方便后面KMP搜索，將其向后移一位，第一位定義為-1，于是有了這樣的一個數組

int prefix[] = {-1,0,0,1,2,3,1};

對應到數組為這樣的形式

當我們遍歷text字符串時，若發現第j位Pattern不匹配時候我們這樣處理（KMP匹配就不贅述了）

如圖，我們在pattern字符串第2位發現A和B不匹配，我們這時候查找前綴表數組，發現第2位對應著是0，這時則將pattern第0位移動到這里j = prefix[j] = 0，如圖。

如此往復，每次發現不匹配則將前綴表對應數字的下標的位置向后移動，如果移動到prefix[0]=-1,則將整個pattern向后移動一位（與第-1位移動到第0位一個意思）

按這樣的模式匹配，當我們pattern遍歷完成就可以確定一個匹配的數據，此時若我們還要繼續往下匹配，我們將pattern移動到當前前綴表的數字處，即 j = prefix[j]。于是我們就可以寫出kmp匹配的代碼

void kmp_search(string text, string pattern) {int n = pattern.length(), m = text.length();int i = 0, j = 0;//prefix_table(pattern);//move_prefix_table(n);while (i < m) {if (j == n - 1 && text[i] == pattern[j]) {cout << "Find pattern at" << i - j << endl;j = prefix[j];}if (text[i] == pattern[j]) i++, j++;else {j = prefix[j];if (j == -1) i++, j++;}} }

第一個判斷為判斷當前pattern是否匹配結束

第二個判斷若相等i和j向后移動一位，若不相等如上述按前綴表移動，前綴表數值為-1時移動一位。

前綴表構建

至此，我們已經了解了怎么通過前綴表匹配，現在要來構造前綴表。若是通過暴力枚舉，仍然要花費很大的時間復雜度構建前綴表，于是需要通過之前的數據和規律來構造

0 A0 AB1 ABA2 ABAB3 ABABA1 ABABAA0 ABABAAC

這里我們用整型變量len來表示當前最大前綴長度（這里指的是真前綴，長度小于字符串），用整型變量i來表示當前匹配的位置，如圖第一位永遠為0，于是len = 0。對于接下來的每一個字符串我們只需要判斷新增加的字符pattern[i]是否與pattern[len]相等，若相等則len++；這里仍然存在一個問題,如下圖。

當我們插入第7位‘A’時，此時len=2，i=6，我們發現 pattern[len] != pattern[i]，但是插入的‘A’與字符串開頭相同，所以這種情況下len不能簡單等于0，應該進行如下操作（燈神視頻里講的有些亂可以自己看視頻理解下）。

void prefix_table(string pattern) {prefix[0] = 0;int len = 0;int i = 1;while (i < pattern.length()) {if (pattern[i] == pattern[len]) {len++;prefix[i] = len;i++;}else {if (len > 0) len = prefix[len - 1];else prefix[i++] = len;}} }

這樣我們就完成了前綴表的構建，但記得之前還提到過需要將前綴表向前移動一位利于KMP搜索，于是還需如下函數（在函數中無法動態獲取數組大小，于是當做參數傳入）。

void move_prefix_table(int n) {int i;for (int i = n; i > 0; i--) prefix[i] = prefix[i - 1];prefix[0] = -1; }

于是整合全部功能就完成了KMP搜索。

#include<bits/stdc++.h> using namespace std; const int N = 1e5+10; int prefix[N];void prefix_table(string pattern) {prefix[0] = 0;int len = 0;int i = 1;while (i < pattern.length()) {if (pattern[i] == pattern[len]) {len++;prefix[i] = len;i++;}else {if (len > 0) len = prefix[len - 1];else prefix[i++] = len;}} } //向前移一位，prefix[0] = -1 void move_prefix_table(int n) {int i;for (int i = n; i > 0; i--) prefix[i] = prefix[i - 1];prefix[0] = -1; }void kmp_search(string text, string pattern) {int n = pattern.length(), m = text.length();int i = 0, j = 0;prefix_table(pattern);move_prefix_table(n);while (i < m) {if (j == n - 1 && text[i] == pattern[j]) {cout << "Find pattern at" << i - j << endl;j = prefix[j];}if (text[i] == pattern[j]) i++, j++;else {j = prefix[j];if (j == -1) i++, j++;}} }int main() {cin.tie(0);ios::sync_with_stdio(false);string text,pattern;cin >> text >>pattern;kmp_search(text,pattern);return 0; }

總結

以上是生活随笔為你收集整理的KMP算法理解（参考BILIBILI正月点灯笼）的全部內容，希望文章能夠幫你解決所遇到的問題。

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