C和C加加文本搜索中的精確匹配演算法上

在文本內容中，都是以字元串的方式來表示，此時要精確搜索文本中是否存在目標文本，也即是搜索在大字元串中搜索目標字元串。這種精確匹配在計算機系統中有著較為廣泛的應用，如文本編輯，拼寫檢查，情報搜索，互聯網搜索等。

較為常見的字元串精確匹配演算法有以下幾種：

1，BF演算法

BF即英文Brute Force 演算法是演算法模式匹配中最簡單，最直觀的演算法。該演算法的基本思想是從主字元串T(t0,t1,t2,t3,….tn-1)中的第m個字元起和目標第1個字元比較，如果相等，則繼續逐個比較後續字元；比較過程中一旦發現不相等，則回溯到源字元串的m+1個字元，重新匹配，依次類推，知道目標字元串每個字元和源字元串的一個連續的字元序列相等，就匹配成功，否則匹配失敗。

想要一起學習C++的可以加裙二四八八九四四三零，裙內有各種資料滿足大家，歡迎加裙

2，MP演算法

MP演算法是對BF演算法的極大改進，利用了已經得到的並且存貯的比較結果，在後續比較過程中直接調用這些比較結果，大大的提高了演算法的效率。在MP演算法中，，最為關鍵的是尋找匹配失效函數，而一旦目標字元串給定，不管源字元串的取值如何，失效函數均為同一個，也即是失效函數與源字元串無關。

下面給出目標字元串的失效函數C語言代碼實現方法：

voidpreMP(const char *dest, intm,intmpnext[])

{

inti, j;

i=0;

j=mpnext[0]=-1;

while(i

{

while(j>-1 && x[i]!=x[j])

j=mpnext[j];

mpnext[++i]=++j;

}

}

其中函數的參數說明如下：

dest：目標字元串

m:目標字元串的長度

mpnext:用來存貯失效發生時下一輪比較的目標字元串的起始比較位置。

想要一起學習C++的可以加裙二四八八九四四三零，裙內有各種資料滿足大家，歡迎加裙

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！