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

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

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

BF(Brute Force)算法

Brute-Force算法的基本思想：

從目標(biāo)串s 的第一個字符起和模式串t的第一個字符進(jìn)行比較，若相等，則繼續(xù)逐個比較后續(xù)字符，否則從串s 的第二個字符起再重新和串t進(jìn)行比較。

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

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

主串 BBC ABB ABCF

子串 ABC

在主串中找出子串的位置，對應(yīng)了其實(shí)就是javascript的indexOf查找方法的實(shí)現(xiàn)了

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

這里值得注意：

1：最外圍循環(huán)的次數(shù)sourceLength - searchLength，因?yàn)槲覀兤ヅ涞哪复辽僖笥诘扔谧哟?/p>

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

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

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

優(yōu)化算法（一）

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

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

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

優(yōu)化算法（二）

i就是主串的下標(biāo)定位，j就是子串的下標(biāo)定位

當(dāng)主串子串相等的時候，就進(jìn)入了子串的循環(huán)模式，當(dāng)子循環(huán)的次數(shù)j滿足子串長度時，就驗(yàn)證是完全匹配

當(dāng)主串子串不相等的時候，就需要把主串的下標(biāo)往后移一位，當(dāng)然i的時候，因?yàn)榭赡芙?jīng)過子串的處理，所以需要i-j+1, 然后復(fù)位子串

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

基于BF算法的四種結(jié)構(gòu),for/while/遞歸

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

JavaScript中數(shù)據(jù)結(jié)構(gòu)與算法(四)：串(BF)_javascript技巧

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

推薦度：

點(diǎn)擊下載本文 文檔為doc格式