一、數(shù)據(jù)結(jié)構(gòu)“串”的模式匹配算法中的BF算法里的i-j2

i-j+2就是匹配不成功然后指針回到起始位置再加1。

i-j+2 == i-(j-1)+1;

j-1是j移動(dòng)的距離（j看作從1開(kāi)始，而不是從0開(kāi)始）；i-（j-1）是i回到與子串比較的起始位置（不是一直回到i=1，i在多次匹配中不斷的變大）。

然后[i-(j-1)] +1 就是回到起始位置之后再往后進(jìn)一位。

例如名列前茅次匹配的時(shí)候，開(kāi)始時(shí)i=1，j=1； 然后匹配失敗，回溯后i+1，第二次匹配開(kāi)始時(shí)就是i=2，j=1。再匹配失敗，回溯到起始位置i=2后 i+1，第三次匹配開(kāi)始時(shí)就是i=3，j=1；以此類推。

i=i-j+2 是數(shù)組下標(biāo)從1開(kāi)始的情況；

i=i-j+1 是數(shù)組下標(biāo)從0開(kāi)始的情況。

BF算法

BF算法介紹

Brute-Force簡(jiǎn)稱為BF算法，亦稱為簡(jiǎn)單匹配算法，采用窮舉的思想。

S：a a a a b c d? 主串：正文串

T：???????? a b c???? 子串：模式串

算法的思路是從S的每一個(gè)字符開(kāi)始依次與T的字符進(jìn)行匹配。

BF算法設(shè)計(jì)思想

Index_BF(S, T)

將主串的第pos個(gè)字符和模式串的名列前茅個(gè)字符比較,

若相等，繼續(xù)逐個(gè)比較后續(xù)字符;

若不等，從主串的下一字符起，重新與模式串的名列前茅個(gè)字符比較。

直到主串的一個(gè)連續(xù)子串字符序列與模式串相等。返回值為S中與T匹配的子序列名列前茅個(gè)字符的序號(hào)即匹配成功。

否則，匹配失敗，返回值-1。

延伸閱讀：

二、KMP算法

KMP算法是一種字符串匹配算法，是由D.E.Knuth，J.H.Morris和V.R.Pratt提出的。其核心是利用字符串匹配失敗后的的信息從而減少字符串與模式串的匹配次數(shù)從而提高字符串匹配的效率。

假設(shè)主串為s=”ababcabdabcabca”、模式串為p=”abcabc”，指針i、j分別指示主串和模式串所比較字符的位序號(hào)。

在名列前茅趟匹配中，由于,,,因此i=2,j=2;

按照之前的思路，我們應(yīng)當(dāng)修改i為1，j為0后再次進(jìn)行比較。但由于,,因而,所以此時(shí)不必從i為1處進(jìn)行匹配，而只需匹配和;

在第三趟匹配中，由于,顯然此時(shí)有，。因?yàn)?,所以無(wú)需與和進(jìn)行比較，而只需匹配和；又因?yàn)?所以,這兩次比較也可以通過(guò)前次匹配的信息來(lái)略過(guò)；

通過(guò)以上的分析，我們不難發(fā)現(xiàn)，我們可以利用模式串自身的信息來(lái)計(jì)算模式串匹配失敗后下一次所要匹配的位置，而主串的比較位置不需要回退。

當(dāng)某次匹配失敗時(shí)，有那么 = 。如果在模式串中存在這樣的k，使得 = ,那么在下一次匹配時(shí)，我們便只需匹配和。特別地，當(dāng)k=0時(shí)，我們應(yīng)當(dāng)匹配和。(k應(yīng)當(dāng)使得…最長(zhǎng))

通過(guò)以上的分析，我們可以知道其實(shí)該算法的關(guān)鍵在于獲取一個(gè)next數(shù)組，通過(guò)該數(shù)組來(lái)記錄模式串中各個(gè)位置的最長(zhǎng)前綴子串從而避免重復(fù)匹配的出現(xiàn)。也就是說(shuō)模式串每次開(kāi)始匹配的位置由模式串本身來(lái)決定。