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

 　　這篇文章主要介紹了JavaScript中數據結構與算法(四)：串(BF),串是由零個或多個字符組成的有限序列,又叫做字符串,本文著重講解了BF(Brute Force)算法,需要的朋友可以參考下

　　串是由零個或多個字符組成的有限序列，又叫做字符串

　　串的邏輯結構和線性表很相似的，不同的是串針對是是字符集，所以在操作上與線性表還是有很大區別的。線性表更關注的是單個元素的操作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查找方法的實現了

　　?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 var sourceStr = "BBC ABB ABCF"; var searchStr = "ABC";   function BF_Ordinary(sourceStr, searchStr) { var sourceLength = sourceStr.length; var searchLength = searchStr.length; var padding = sourceLength - searchLength; //循環的次數 //BBC ABB ABCF =>ABC => 搜索9次 for (var i = 0; i <= padding; i++) { //如果滿足了第一個charAt是相等的 //開始子循環檢測 //其中sourceStr的取值是需要疊加i的值 if (sourceStr.charAt(i) == searchStr.charAt(0)) { //匹配成功的數據 var complete = searchLength; for (var j = 0; j < searchLength; j++) { if (sourceStr.charAt(i + j) == searchStr.charAt(j)) { --complete if (!complete) { return i; } } } } } return -1; }

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

　　這裡值得注意：

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

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

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

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

　　優化算法(一)

　　?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 function BF_Optimize(sourceStr, searchStr) { var mainLength = sourceStr.length; var searchLength = searchStr.length; var padding = mainLength - searchLength; for (var offset = 0; offset <= padding; offset++) { var match = true; for (var i = 0; i < searchLength; i++) { //取反,如果只要不相等 if (searchStr.charAt(i) !== sourceStr.charAt(offset + i)) { match = false; break; } } if (match) return offset; } return -1; }

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

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

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

　　優化算法(二)

　　?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 function BF_Optimize_2(sourceStr, searchStr) { var i = 0, j = 0;   while (i < sourceStr.length) { // 兩字母相等則繼續 if (sourceStr.charAt(i) == searchStr.charAt(j)) { i++; j++; } else { // 兩字母不等則角標後退重新開始匹配 i = i - j + 1; // i 回退到上次匹配首位的下一位 j = 0; // j 回退到子串的首位 }   if (j == searchStr.length) { return i - j; }   } }

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

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

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

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

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

　　?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99