樸素模式匹配算法和KMP匹配算法

一、樸素模式

假設我們要從主串S=”goodgoogle"中找到子串T=“google"的位置，步驟如下：

i表示主串的當前位置下標，j表示子串的當前位置下標，如上圖在第一輪比較（i=1開始）中j=4和i=4的位置不匹配，接下來就要指針回退，從i=2開始比較，如下：

如此反復直到比較到 i =（主串長度-子串長度+1）的位置或者 j = 子串的長度 就退出比較循環，上面的主串和子串在比較到i=5的位置就完全匹配了。

#include <stdio.h>int Index(const char S[], const char T[], int pos){int i = pos; //主串當前下標int j = 1; //子串當前下標//S[0]是主串的長度，T[0]是子串的長度while(i <= S[0] && j <= T[0]){//如果相等則繼續向下比較if(S[i] == T[j]) {++i;++j;//如果不等則指針回退}else{i = i - j + 2; //主串回退j = 1;}}//j>T[0]則說明子串被完全匹配if( j > T[0]) return i - T[0];else return 0; }int main(){char S[] = {10, 'g', 'o', 'o', 'd', 'g', 'o', 'o','g', 'l', 'e'}; char T[] = {6, 'g', 'o', 'o', 'g', 'l', 'e'};int i = Index(S, T, 1);printf("%d\n", i);return 0; }

分析一下這種匹配算法最好的情況時間復雜度是O(m)，即主串的前m個字符剛好與子串相等，最壞的情況是每次最后一個字符不匹配，時間復雜度是O(m*n) m是主串長度n是子串的長度。

樸素模式匹配算法時間復雜度分析如下：（n為主串長度，m為模式串長度）

時間復雜度:

最好情況
O(1) 一開始就匹配成功。

最壞情況
O((n-m+1)*m) 每次不成功的匹配都發生在模式串的最后一個字符。

平均情況
O(n+m) 根據等概率原則，平均是(n+m)/2次查找。

二、KMP算法

像二進制這樣的多個0和1重復的字符串，上面的模式匹配需要挨個遍歷是非常慢的，KMP算法可以大大避免重復遍歷的情況。

下面我們來看看KMP算法的基本原理

如上，可以看到主串S和子串T在第一輪比較的時候，前面5個相等，只有i=6和j=6的位置不等。由于子串T中abcde這5個字符本身互不相等，可以知道子串T中a就不可能和j=2、3、4、5的位置的字符相等。所以可以直接跳到i=6的位置進行比較。

再看上圖，如果子串T中存在重復的元素（比如j=1,2和j=4,5處的字符），按照上面的分析，我們可以直接跳到i=4的位置比較，但是我們已經知道j=1,2和j=4,5相等，并且i=4,5和j=4,5相等，所以可以不用比較i=4,5和j=1,2。

KMP模式匹配算法就是為了不讓i指針回退，既然i值不回退，我們就要考慮變化j的值了。通過上面的觀察可以發現，j值的變化與主串其實沒有什么關系，而是取決于子串T中是否有重復問題。

我們把T串各個位置的j值的變化定義為一個數組next,那么next的長度就是T串的長度，可以得到下面函數：

#include <stdio.h>void get_next(const char T[], int *next){int i,j;i = 1;j = 0;next[1] = 0;//T[0]是子串T的長度while(i < T[0]){//T[i]表示后綴的單個字符//T[j]表示前綴的單個字符if( j==0 || T[i] == T[j]){++i;++j;next[i] = j;}else{j = next[j];}} }int Index_KMP(const char S[], const char T[], int pos){int i = pos;int j = 1;int next[255];get_next(T, next);while(i <= S[0] && j <= T[0]){//相對于樸素算法，增加了一個j==0的判斷if( j==0 || S[i] == T[j]){++i;++j;}else{//j回退到合適的位置，i的值不變j = next[j];}}if( j>T[0]){return i-T[0];}else{return 0;} } int main(){return 0; }

整個算法的時間復雜度為O（n+m）

總結

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

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