《數(shù)據(jù)結(jié)構(gòu)與算法之美》，王爭 著

標(biāo)簽：數(shù)據(jù)結(jié)構(gòu)、算法

第8章 字符串匹配算法

一、BF算法（暴力匹配算法）

這一部分介紹了

• BF算法的原理和實(shí)現(xiàn)

• BF算法的性能分析

• 編程語言中的查找、替換函數(shù)是怎樣實(shí)現(xiàn)的

筆記：很多實(shí)際應(yīng)用中，模式串和主串的長度都不會太長，BF算法本身代碼編程非常簡單，不容易出bug，再加上在匹配過程中，出現(xiàn)失配即可提前終止算法，所以在實(shí)際的軟件開發(fā)中，絕大部分情況下，BF算法就夠用了；

常用的編程語言中提供的字符串查找函數(shù)采用的算法就是BF算法（時(shí)間復(fù)雜度最壞是O(nm)）。如果字符串匹配是軟件的核心功能或性能瓶頸時(shí)，開發(fā)人員就不能使用編程語言提供的現(xiàn)成函數(shù)了（因?yàn)橐话愣际荁F算法），而是要依據(jù)數(shù)據(jù)特點(diǎn)、性能要求、選擇合適的字符串匹配算法從零開始編程實(shí)現(xiàn)。

另外，字符串匹配算法的性能分析需要涉及兩個(gè)變量：主串和模式串的長度，這也是要注意的。

二、RK算法（Rabin-Karp算法）

這一部分介紹了

• RK算法的原理與實(shí)現(xiàn)

• RK算法的性能分析

筆記：RK算法是借助哈希算法對BF算法進(jìn)行改造，時(shí)間復(fù)雜度為O(n)。

三、BM算法（Boyer-Moore算法）

這一部分介紹了

• BM算法的核心思想

• BM算法的原理分析

• BM算法的代碼實(shí)現(xiàn)（書中篇幅較長）

• BM算法的性能分析

筆記：BM算法原理復(fù)雜，理解困難，但它是一種非常高效的字符串匹配算法，時(shí)間復(fù)雜度比RK算法低，在實(shí)際的軟件開發(fā)中應(yīng)用比較多。

四、KMP算法（Knuth-Morris-Pratt算法）

這一部分介紹了

• KMP算法的基本原理

• 失效函數(shù)的計(jì)算方法

• KMP算法的性能分析

筆記：KMP算法的時(shí)間復(fù)雜度O(m+n)。KMP算法借鑒了BM算法的思想。學(xué)習(xí)KMP算法最復(fù)雜的是next數(shù)組的計(jì)算。

五、Trie樹

這一部分介紹了

• Trie樹的定義

• Trie樹的代碼實(shí)現(xiàn)

• Trie樹的性能分析

• Trie樹與哈希表、紅黑樹的比較

• Trie樹的應(yīng)用：搜索引擎的搜索關(guān)鍵詞提示功能

筆記：Trie樹是一種非常高效的字符串匹配算法，借助空間換時(shí)間的思路。特別適合查找前綴匹配的字符串。

六、AC自動機(jī)

這一部分介紹了

基于單模式串的敏感詞過濾

基于Trie樹的敏感詞過濾

基于AC自動機(jī)的敏感詞過濾

AC自動機(jī)的性能分析

筆記：AC自動機(jī)是基于Trie樹的一種改進(jìn)結(jié)構(gòu)，也借鑒了KMP算法中的next數(shù)組的思想。多模式匹配算法是為了快速地在主串中查找多個(gè)模式串，適合模式串集合不頻繁更新的場景，如敏感詞過濾系統(tǒng)。

本章筆記：模式串和主串的匹配過程可以看成模式串在主串中不停地往后滑動。當(dāng)遇到不匹配時(shí)，如何跳過一些肯定不會匹配的情況，將模式串往后多滑動幾位，這樣字符串匹配算法的性能就提高了。學(xué)習(xí)字符串匹配算法，除了字符串匹配問題是一種常見應(yīng)用以外，學(xué)習(xí)各種字符串匹配算法也能鍛煉程序員算法設(shè)計(jì)的水平和能力。