提起字符串匹配，可能很多人都會想到KMP算法 O(m+n)，但是其實KMP並不常用，因為依然是慢的，常用的其實是BM算法 O(m/n)（Boyer-Moore算法），這就是很多文本編輯器的查找功能採用的算法，而Sunday算法是在其之上又做了一些改動。 

思路

先說下BM算法

其核心就是兩個啟發策略：

（1）壞字符算法

當出現一個壞字符時, BM算法向右移動模式串, 讓模式串中最靠右的對應字符與壞字符相對，然後繼續匹配。壞字符算法有兩種情況。

Case1：模式串中有對應的壞字符時，讓模式串中最靠右的對應字符與壞字符相對（PS：BM不可能走回頭路，因為若是回頭路，則移動距離就是負數了，肯定不是最大移動步數了），如下圖。

Case2：模式串中不存在壞字符，很好，直接右移整個模式串長度這麼大步數，如下圖。

（2）好後綴算法

如果程序匹配了一個好後綴, 並且在模式中還有另外一個相同的後綴或後綴的部分, 那把下一個後綴或部分移動到當前後綴位置。假如說，pattern的後u個字符和text都已經匹配了，但是接下來的一個字符不匹配，我需要移動才能匹配。如果說後u個字符在pattern其他位置也出現過或部分出現，我們將pattern右移到前面的u個字符或部分和最後的u個字符或部分相同，如果說後u個字符在pattern其他位置完全沒有出現，很好，直接右移整個pattern。這樣，好後綴算法有三種情況，如下圖所示：

Case1：模式串中有子串和好後綴完全匹配，則將最靠右的那個子串移動到好後綴的位置繼續進行匹配。

Case2：如果不存在和好後綴完全匹配的子串，則在好後綴中找到具有如下特徵的最長子串,使得P[m-s…m]=P[0…s]。

Case3：如果完全不存在和好後綴匹配的子串，則右移整個模式串。

（3）移動規則

BM算法的移動規則是：

將3中算法基本框架中的j += BM()，換成j += MAX（shift（好後綴），shift（壞字符）），即

BM算法是每次向右移動模式串的距離是，按照好後綴算法和壞字符算法計算得到的最大值。

shift（好後綴）和shift（壞字符）通過模式串的預處理數組的簡單計算得到。壞字符算法的預處理數組是bmBc[]，好後綴算法的預處理數組是bmGs[]。

而這兩個算法的具體實現，這裡不再說，請移步前輩的文章觀看： grep之字符串搜索算法Boyer-Moore由淺入深

知道了BM算法，下面我們來說Sunday算法

Sunday算法

Sunday算法是從前往後匹配（BM是從後往前），關注的是主串中參與匹配的最末字符（並非正在匹配、或者說參與比較的）的下一位，好好記住這句話，因為這裡是Sunday算法裡最不容易理解的地方了，對，最不容易，而且還是個單純的文字理解

Sunday算法只有一個啟發策略

Case1

：如果關注的字符沒有在子串中出現則直接跳過

即移動位數 = 子串長度 + 1；

Case2： 否則，其

移動位數 = 子串長度 - 該字符最右出現的位置(以0開始)

或者移動位數 = 子串中該字符最右出現的位置到尾部的距離 + 1

看下例子：

簡直簡單的不像話，但是其實簡單想一下就知道，這個算法缺點也很明顯，有得有失嘛，這個是必然的

缺點

如果是下面這個情況，會怎麼樣？

主串：baaaabaaaabaaaabaaaa

子串：aaaaa

沒錯，這個時候，效率瞬間變成了O(m*n)

Sunday算法的移動是取決於子串的，這一點跟BM算法沒什麼區別，當這個子串重複很多的時候，就會非常糟糕了

大家知道這一點，然後有所取捨，就好啦，下面上代碼吧

代碼

實例：