前言
慣例届慈，最重要的匹配思路還是要貼一遍：
- 將
模式串和主串進(jìn)行比較- 從前往后比較
- 從后往前比較
- 匹配時润匙，比較
主串和模式串的下一個位置 - 失配時,
- 在
模式串中尋找一個合適的位置- 如果找到琅关，從這個位置開始與
主串當(dāng)前失配位置進(jìn)行比較 - 如果未找到革骨，從
模式串的頭部與主串失配位置的下一個位置進(jìn)行比較
- 如果找到琅关，從這個位置開始與
- 在
主串中找到一個合適的位置，重新與模式串進(jìn)行比較
- 在
Sunday算法也許是三種里面最好理解也最好寫的一種了屉符，它的思路也是在于失配時如何跳過盡可能多的字符剧浸，具體的說，主要是優(yōu)化了第3步矗钟，失配時唆香，在主串中找到一個合適的位置，重新與模式串進(jìn)行比較吨艇。
算法介紹與分析
- 從
主串和模式串的首位開始比較躬它，記- 主串
S - 模式串
P - 主串長度
slen - 模式串長度
plen - 主串位置指針
i - 模式串位置指針
j - 每次重新匹配時，模式串尾部對應(yīng)主串位置的下一位
m
- 主串
- 判斷
S[i]與P[j]是否相等- 如果相等
- 判斷
j與plen-1是否相等东涡，如果相等則表示 表示模式串匹配完成冯吓，直接返回i - j即可 - 如果不相等，則繼續(xù)比較下一位疮跑，即
i++;j++;
- 判斷
- 如果不相等
- 查看
S[m]字符是否存在于P中组贺，如果存在，將P移至兩字符對應(yīng)的位置上 - 如果不存在祖娘，則移至
S[m]的后一位
- 查看
- 如果相等
- 如果移動后失尖，
m > slen，說明S已經(jīng)遍歷一遍渐苏，仍然沒有找到目標(biāo)掀潮，模式串匹配失敗。
栗子
初始狀態(tài)整以，i = 0, j = 0, m = 4
比較 S[0] 和 P[0]胧辽，發(fā)現(xiàn)不相等峻仇，看 S[4] 處發(fā)現(xiàn)并沒有在 P 中出現(xiàn)
直接將 P 移至 S[4] 的后一位公黑，此時 i = 5, j = 0, m = 9
比較 S[5] 和 P[0]，發(fā)現(xiàn)不相等，看 S[9] 處發(fā)現(xiàn)有在 P 中出現(xiàn)
將 P 中的 i 與 S 中的 i 對齊凡蚜，此時 i = 8, j = 0, m = 12
比較 S[8] 和 P[0]人断，發(fā)現(xiàn)不相等，看 S[12] 處發(fā)現(xiàn)并沒有在 P 中出現(xiàn)
直接將 P 移至 S[12] 的后一位朝蜘，此時 i = 13, j = 0, m = 17
比較 S[13] 和 P[0]恶迈，發(fā)現(xiàn)不相等，看 S[17] 處發(fā)現(xiàn)有在 P 中出現(xiàn)
將 P 中的 n 與 S 中的 n 對齊谱醇，此時 i = 15, j = 0, m = 18
繼續(xù)匹配暇仲，直到 j === plen - 1 = 3，則匹配成功副渴，得到結(jié)果 i - j = 18 - 3 = 15
代碼實現(xiàn)
極端情況的排除
整體邏輯框架
- 首先奈附，肯定有一個循環(huán)，先找到終結(jié)條件煮剧，和
BF算法一樣斥滤，查找順序也是從前往后，可以很快知道勉盅，i < slen就是終結(jié)的條件 - 其次佑颇，就是要對匹配和失配進(jìn)行不同的處理
由此，我們就可以寫出整體的框架：
細(xì)節(jié)的完善
總結(jié)
Sunday算法 遵循匹配思路草娜，失配時采取自己的優(yōu)化策略挑胸，也盡可能的移動了最多的步數(shù)，達(dá)到提高效率的目的驱还，且易理解嗜暴。
后記
“字符串匹配算法”是“重學(xué)數(shù)據(jù)結(jié)構(gòu)與算法”系列筆記：
