給定兩個字符串S和T，在主串S中查找子串T的過程稱為串匹配（string
matching，也稱模式匹配），T稱為模式。這里將介紹處理串匹配問題的兩種算法，BF算法和KMP算法。

BF算法

（暴力匹配算法）

BF算法簡介

F(Brute Force)算法是普通的模式匹配算法，BF算法的思想就是將目標串S的第一個字符與模式串T的第一個字符進行匹配，若相等，則繼續(xù)比較S的第二個字符和 T的第二個字符；若不相等，則比較S的第二個字符和T的第一個字符，依次比較下去，直到得出最后的匹配結果。

BF算法原理

首先，給定 “主串” 和 “模式串” 如下：

BF算法使用簡單粗暴的方式，對主串和模式串進行逐個字符的比較：




檢測到字符不匹配，模式串向后挪動一位，和主串的第二個等長子串比較。

檢測到字符不匹配，模式串繼續(xù)向后挪動一位，和主串的第三個等長子串比較

···········不斷循環(huán)上面步驟，直到匹配成功或者匹配失敗（即到主串末尾結束）。

算法

int BF(char* S, char* T) {int sLen = strlen(S); //文本串長度int tLen = strlen(T); //模式串長度int i = 0;int j = 0;while (i < sLen && j < tLen){if (S[i] == T[j]){//①如果當前字符匹配成功（即S[i] == T[j]），則i++，j++i++;j++;}else{//②如果失配（即S[i]! = T[j]），令i = i - (j - 1)，j = 0i = i - j + 1;j = 0;}}//匹配成功，返回模式串t在文本串s中的位置，否則返回-1if (j == tLen)return i - j;elsereturn -1; }

測試

#include<stdio.h> #include <stdlib.h> #include <string.h>int BF(char* S, char* T) {int sLen = strlen(S); //文本串長度int tLen = strlen(T); //模式串長度int i = 0;int j = 0;while (i < sLen && j < tLen){if (S[i] == T[j]){//①如果當前字符匹配成功（即S[i] == T[j]），則i++，j++i++;j++;}else{//②如果失配（即S[i]! = T[j]），令i = i - (j - 1)，j = 0i = i - j + 1;j = 0;}}//匹配成功，返回模式串t在文本串s中的位置，否則返回-1if (j == tLen)return i - j;elsereturn -1; }int main() {char S[] = "ABC ABCDAB ABCDABCDABDW";char T[] = "ABCDABD";int num;char *ch = T;num = BF(S,T);if (num >= 0){printf("matched @: %s\n", ch);}else{printf("matched fail!\n");}return 0; }

執(zhí)行結果：

matched @: ABCDABD

總結：BF算法比較直接，是一種蠻力法，該算法最壞情況下要進行m*(n-m+1)次比較，時間復雜度為O(m*n)，下面來看一個效率非常高的字符串匹配算法，即KMP算法。

KMP算法

KMP算法簡介

之所以叫做KMP，是因為這個算法是由Knuth、Morris、Pratt三個提出來的，取了這三個人的名字的頭一個字母。KMP算法的關鍵是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達到快速匹配的目的。具體實現(xiàn)就是實現(xiàn)一個next()函數(shù)，函數(shù)本身包含了模式串的局部匹配信息。時間復雜度O(m+n)。

簡單理解就是：KMP算法是拿來處理字符串匹配的。換句話說，給你兩個字符串，你需要回答，B串是否是A串的子串（A串是否包含B串）。

KMP算法原理

（參考自：看，未來的博客）
首先，給定 “主串” 和 “模式串” 如下：

第一輪，模式串和主串的第一個等長子串比較，發(fā)現(xiàn)前5個字符都是匹配的，第6個字符不匹配，是一個“壞字符”：

這時候，我們可以有效利用已匹配的前綴 “GTGTG” 。通過觀察我們可以發(fā)現(xiàn)，在前綴“GTGTG”當中，后三個字符“GTG”和前三位字符“GTG”是相同的：

在下一輪的比較時，只有把這兩個相同的片段對齊，才有可能出現(xiàn)匹配。這兩個字符串片段，分別叫做最長可匹配后綴子串和最長可匹配前綴子串。

第二輪，我們直接把模式串向后移動兩位，讓兩個“GTG”對齊，繼續(xù)從剛才主串的壞字符A開始進行比較：

顯然，主串的字符A仍然是壞字符，這時候的匹配前綴縮短成了GTG：

按照第一輪的思路，我們來重新確定最長可匹配后綴子串和最長可匹配前綴子串：

第三輪，我們再次把模式串向后移動兩位，讓兩個“G”對齊，繼續(xù)從剛才主串的壞字符A開始進行比較：

·········接下來還是重復步驟，就不往寫了。

next數(shù)組

什么是next數(shù)組？next數(shù)組用來干什么？
next數(shù)組是決定kmp算法快速移動的核心。

next數(shù)組的生成示例：

說白了就是把子串拆分，然后看尾部有多少個字符重復，沒有寫-1，有一個就寫0，有兩個寫1，依次類推（你也可以寫0，1，2，具體想寫啥看個人吧，我這里只是全部減1了，當然在代碼里也要記得修改）。

有了next數(shù)組，我們就可以通過已匹配前綴的下一個位置（壞字符位置），快速尋找到最長可匹配前綴的下一個位置，然后把這兩個位置對齊。

算法

void compute_prefix(const char *pattern, int next[]) {int i; //前綴int j = -1; //前綴尾巴const int m = strlen(pattern);next[0] = j;for (i = 1; i < m; i++){while (j > -1 && pattern[j + 1] != pattern[i]) //前后綴不相等{j = next[j];}if (pattern[i] == pattern[j + 1]) //前后綴相等{j++;}next[i] = j;} }int kmp(const char *text, const char *pattern) {int i;int j = -1;const int n = strlen(text);const int m = strlen(pattern);if (n == 0 && m == 0) return 0;if (m == 0) return 0;int *next = (int*)malloc(sizeof(int) * m);compute_prefix(pattern, next);for (i = 0; i < n; i++){while (j > -1 && pattern[j + 1] != text[i]) j = next[j];if (text[i] == pattern[j + 1]) j++;if (j == m - 1){free(next);return i-j;}}free(next);return -1; }

測試

#include<stdio.h> #include <stdlib.h> #include <string.h>void compute_prefix(const char *pattern, int next[]) {int i; //前綴int j = -1; //前綴尾巴const int m = strlen(pattern);next[0] = j;for (i = 1; i < m; i++){while (j > -1 && pattern[j + 1] != pattern[i]) //前后綴不相等{j = next[j];}if (pattern[i] == pattern[j + 1]) //前后綴相等{j++;}next[i] = j;} } int kmp(const char *text, const char *pattern) {int i;int j = -1;const int n = strlen(text);const int m = strlen(pattern);if (n == 0 && m == 0) return 0;if (m == 0) return 0;int *next = (int*)malloc(sizeof(int) * m);compute_prefix(pattern, next);for (i = 0; i < n; i++){while (j > -1 && pattern[j + 1] != text[i]) j = next[j];if (text[i] == pattern[j + 1]) j++;if (j == m - 1){free(next);return i-j;}}free(next);return -1; } int main() {char text[] = "ABC ABCDAB ABCDABCDABDE";char pattern[] = "ABCDABD";char *ch = pattern;int i = kmp(text, pattern);if (i >= 0){printf("matched @: %s\n", ch);}else{printf("matched fail!\n");}return 0; }

執(zhí)行結果：

matched @: ABCDABD

總結

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

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