JavaScript中數據結構與算法(四)：串(BF)_javascript技巧

串的邏輯結構和線性表很相似的，不同的是串針對是是字符集，所以在操作上與線性表還是有很大區別的。線性表更關注的是單個元素的操作CURD，串則是關注查找子串的位置，替換等操作。

當然不同的高級語言對串的基本操作都有不同的定義方法，但是總的來說操作的本質都是相似的。比如javascrript查找就是indexOf, 去空白就是trim,轉化大小寫toLowerCase/toUpperCase等等

這里主要討論下字符串模式匹配的幾種經典的算法：BF、BM、KMP

BF(Brute Force)算法

Brute-Force算法的基本思想：

從目標串s 的第一個字符起和模式串t的第一個字符進行比較，若相等，則繼續逐個比較后續字符，否則從串s 的第二個字符起再重新和串t進行比較。

依此類推，直至串t 中的每個字符依次和串s的一個連續的字符序列相等，則稱模式匹配成功，此時串t的第一個字符在串s 中的位置就是t 在s中的位置，否則模式匹配不成功

可見BF算法是一種暴力算法，又稱為樸素匹配算法或蠻力算法。

主串 BBC ABB ABCF

子串 ABC

在主串中找出子串的位置，對應了其實就是javascript的indexOf查找方法的實現了

BF算法就是簡單粗暴，直接把BBC ABB ABCF母串的每一個字符的下表取出來與模式串的第一個字符匹配，如果相等就進去字串的再次匹配

這里值得注意：

1：最外圍循環的次數sourceLength - searchLength，因為我們匹配的母串至少要大于等于子串

2：在子串的繼續匹配中，母串的起點是需要疊加的(i+j)

3：通過一個條件判斷是否完全匹配complete，BBC ABB ABCF中，我們在ABB的時候就需要跳過去

上面是最簡單的一個算法了，代碼上還有更優的處理，比如在自串的匹配上可以采取取反的算法

優化算法（一）

我們不需要判斷為真的情況，我們只要判斷為假的情況就可以了，當子匹配結束后match沒有被修改過的話，則說明此匹配是完全匹配

以上2種方法我們都用到了子循環，我們能否改成一個循環體呢？

其實我們可以看到規律，主串每次都只會遞增+1，子串每次匹配也是從頭開始匹配，所以我們可以改成一個while，控制下標指針就可以了

優化算法（二）

i就是主串的下標定位，j就是子串的下標定位

當主串子串相等的時候，就進入了子串的循環模式，當子循環的次數j滿足子串長度時，就驗證是完全匹配

當主串子串不相等的時候，就需要把主串的下標往后移一位，當然i的時候，因為可能經過子串的處理，所以需要i-j+1, 然后復位子串

具體我們可以看看代碼比較

基于BF算法的四種結構,for/while/遞歸

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com

JavaScript中數據結構與算法(四)：串(BF)_javascript技巧

JavaScript中數據結構與算法(四)：串(BF)_javascript技巧:串是由零個或多個字符組成的有限序列，又叫做字符串 串的邏輯結構和線性表很相似的，不同的是串針對是是字符集，所以在操作上與線性表還是有很大區別的。線性表更關注的是單個元素的操作CURD，串則是關注查找子串的位置，替換等操作。 當然不同的高級語言對串

推薦度：

點擊下載本文 文檔為doc格式