国产一区二区精品-国产一区二区精品久-国产一区二区精品久久-国产一区二区精品久久91-免费毛片播放-免费毛片基地

千鋒教育-做有情懷、有良心、有品質的職業教育機構

手機站
千鋒教育

千鋒學習站 | 隨時隨地免費學

千鋒教育

掃一掃進入千鋒手機站

領取全套視頻
千鋒教育

關注千鋒學習站小程序
隨時隨地免費學習課程

當前位置:首頁  >  技術干貨  > 數據結構“串”的模式匹配算法中的BF算法里的i-j2中的i,j分別是什么意思呢?

數據結構“串”的模式匹配算法中的BF算法里的i-j2中的i,j分別是什么意思呢?

來源:千鋒教育
發布人:xqq
時間: 2023-10-11 04:21:22 1696969282

一、數據結構“串”的模式匹配算法中的BF算法里的i-j2

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

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

j-1是j移動的距離(j看作從1開始,而不是從0開始);i-(j-1)是i回到與子串比較的起始位置(不是一直回到i=1,i在多次匹配中不斷的變大)。

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

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

i=i-j+2 是數組下標從1開始的情況;

i=i-j+1 是數組下標從0開始的情況。

BF算法

BF算法介紹

Brute-Force簡稱為BF算法,亦稱為簡單匹配算法,采用窮舉的思想。

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

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

算法的思路是從S的每一個字符開始依次與T的字符進行匹配。

BF算法設計思想

Index_BF(S, T)

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

若相等,繼續逐個比較后續字符;

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

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

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

延伸閱讀:

二、KMP算法

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

假設主串為s=”ababcabdabcabca”、模式串為p=”abcabc”,指針i、j分別指示主串和模式串所比較字符的位序號。

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

按照之前的思路,我們應當修改i為1,j為0后再次進行比較。但由于,,因而,所以此時不必從i為1處進行匹配,而只需匹配和;

在第三趟匹配中,由于,顯然此時有,。因為,,所以無需與和進行比較,而只需匹配和;又因為,所以,這兩次比較也可以通過前次匹配的信息來略過;

通過以上的分析,我們不難發現,我們可以利用模式串自身的信息來計算模式串匹配失敗后下一次所要匹配的位置,而主串的比較位置不需要回退。

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

通過以上的分析,我們可以知道其實該算法的關鍵在于獲取一個next數組,通過該數組來記錄模式串中各個位置的最長前綴子串從而避免重復匹配的出現。也就是說模式串每次開始匹配的位置由模式串本身來決定。

聲明:本站稿件版權均屬千鋒教育所有,未經許可不得擅自轉載。
10年以上業內強師集結,手把手帶你蛻變精英
請您保持通訊暢通,專屬學習老師24小時內將與您1V1溝通
免費領取
今日已有369人領取成功
劉同學 138****2860 剛剛成功領取
王同學 131****2015 剛剛成功領取
張同學 133****4652 剛剛成功領取
李同學 135****8607 剛剛成功領取
楊同學 132****5667 剛剛成功領取
岳同學 134****6652 剛剛成功領取
梁同學 157****2950 剛剛成功領取
劉同學 189****1015 剛剛成功領取
張同學 155****4678 剛剛成功領取
鄒同學 139****2907 剛剛成功領取
董同學 138****2867 剛剛成功領取
周同學 136****3602 剛剛成功領取
相關推薦HOT