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

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

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

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

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

　　BF(Brute Force)算法

　　Brute-Force算法的基本思想：

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

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

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

　　主串 BBC ABB ABCF

　　子串 ABC

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

　　?

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

　　這里值得注意：

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

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