前言

一切都要從 LeetCode 的第 28 題 實(shí)現(xiàn) strStr()開(kāi)始說(shuō)起雏门，當(dāng)自己腦子里的第一種暴力查找法寫(xiě)出來(lái)并 AC 之后搓逾，還是覺(jué)得不滿足尺迂，決定把能找到的解法都理解了具温，于是便有了這個(gè)系列。

字符串匹配的整體思路

當(dāng)我理解完四種經(jīng)典的匹配算法之后癞揉，總結(jié)了一下這類操作的核心：

1. 將模式串和主串進(jìn)行比較
   • 從前往后比較
   • 從后往前比較
2. 匹配時(shí)纸肉，比較主串和模式串的下一個(gè)位置
3. 失配時(shí),
   • 在模式串中尋找一個(gè)合適的位置
     • 如果找到，從這個(gè)位置開(kāi)始與主串當(dāng)前失配位置進(jìn)行比較
     • 如果未找到喊熟，從模式串的頭部與主串失配位置的下一個(gè)位置進(jìn)行比較
   • 在主串中找到一個(gè)合適的位置柏肪，重新與模式串進(jìn)行比較

所以總的來(lái)說(shuō)，之所以會(huì)有這么多種匹配算法芥牌，本質(zhì)上就是一些大神對(duì)第1步和第3步進(jìn)行了優(yōu)化烦味，這個(gè)核心思路一定要牢牢的先記在腦子里呼胚，這樣之后理解優(yōu)化的匹配算法就不會(huì)一臉懵逼宵溅。

算法介紹與分析

介紹

BF 算法付呕，Brute-Force(暴力)法的簡(jiǎn)稱灸芳，完全沒(méi)有優(yōu)化，每次失配時(shí)從主串的下一個(gè)位置進(jìn)行比較魔种，直到比較結(jié)束悠栓。

分析

算法描述如下：

1. 將模式串和主串從前往后比較
2. 匹配時(shí)色解，比較主串和模式串的下一個(gè)位置
3. 失配時(shí)痘昌，從主串的下一個(gè)位置開(kāi)始與模式串的頭部重新開(kāi)始比較

我們假設(shè)有 主串 ABABBBAAABABABBA 和 模式串 ABABABB 钥勋，
下面放五張圖來(lái)理解一下這個(gè)過(guò)程：

QQ20200112-160741.png

QQ20200112-161000.png

上面這兩幅圖，表現(xiàn)的是第1步和第2步控汉，可以看出：

1. 從 S[0] 和 P[0] 開(kāi)始從頭往后比較
2. 如果匹配笔诵，比較S[i++]和S[j++]

QQ20200112-161423.png

QQ20200112-161548.png

上面這兩幅圖返吻，則表現(xiàn)的時(shí)第3步姑子，可以看出：

1. 如果 S[i] 和 P[j] 失配
2. j = 0 從 P[0] 也就是模式串頭部開(kāi)始與主串的下一個(gè)位置S[i - (j - 1)]開(kāi)始繼續(xù)進(jìn)行匹配

重復(fù)上述兩步，直到下圖完全匹配或者找不到模式串為止

QQ20200112-162337.png

代碼

思路還是很好理解的测僵，但是代碼怎么寫(xiě)呢街佑？
其實(shí)我一直覺(jué)得刷 LeetCode 除了鞏固與提高數(shù)據(jù)結(jié)構(gòu)與算法的能力之外，最重要的就是訓(xùn)練一種把思路翻譯成代碼的能力捍靠，下面我來(lái)嘗試翻譯一下上述的算法思路沐旨。

1、先進(jìn)行極端情況的排除

carbon.png

這個(gè)操作應(yīng)該是刷題刷多了榨婆，像以前做數(shù)學(xué)題寫(xiě)“解”的操作

2磁携、寫(xiě)出整體的結(jié)構(gòu)

1. 從算法的思路很容易看出，這里的“重復(fù)上訴兩步”良风，明顯是要翻譯成循環(huán)操作
2. 如果是循環(huán)谊迄，那么終止條件是什么闷供，可以很快想到，只有兩種終止情況：
   • 主串中沒(méi)有找到 模式串的匹配统诺，此時(shí) i = haystack.length
   • 主串中找到了模式串的匹配歪脏，此時(shí) j = needle.length
3. 算法處理過(guò)程主要是兩步，所以這里一定有一個(gè)分支結(jié)構(gòu)
   • 匹配
   • 失配
4. 如果沒(méi)找到粮呢，直接 return -1 就好了婿失，但要是找到了，應(yīng)該怎么確定那個(gè) index 的值呢啄寡？根據(jù)上面成功的圖豪硅，我們可以發(fā)現(xiàn)，匹配的位置 8挺物，是等于 主串的末尾 14 減去 模式串的末尾 6 得到的舟误，也就是最后匹配的那個(gè) index = i - j

carbon的副本.png

3、補(bǔ)充具體操作

根據(jù)算法分析里的描述姻乓，很容易知道

1. 匹配嵌溢，i++; j++; 比較各自的下一位
2. 失配，i = i - (j - 1); j = 0;重新進(jìn)行下一輪匹配

carbon的副本2.png

總結(jié)

至此蹋岩，整個(gè)BF算法的分析與編寫(xiě)就完成了赖草，雖然它是一個(gè)毫無(wú)優(yōu)化的結(jié)構(gòu)，但是體現(xiàn)出了所有字符串匹配算法的基本思想剪个，計(jì)算機(jī)不是人秧骑，可以通過(guò)眼睛觀察和大腦思考來(lái)進(jìn)行定位，它只能通過(guò)一個(gè)一個(gè)字符的比較來(lái)進(jìn)行判定扣囊，接下來(lái)的算法乎折，就開(kāi)始運(yùn)用到一些騷操作來(lái)進(jìn)行優(yōu)化這個(gè)匹配的過(guò)程。

后記

“字符串匹配算法”是“重學(xué)數(shù)據(jù)結(jié)構(gòu)與算法”系列筆記中的一個(gè)章節(jié)侵歇，細(xì)分為以下幾個(gè)部分骂澄，之后會(huì)陸續(xù)填坑。

• 字符串匹配算法(一)——BF算法
• 字符串匹配算法(二)——KMP算法
• 字符串匹配算法(三)——BM算法
• 字符串匹配算法(四)——Sunday算法