5. 擴展 2：Sunday 算法

上文中，我們已經(jīng)介紹了 KMP 算法和 BM 算法，這兩個算法在最壞情況下均具有線性的查找時間。但實際上，KMP 算法并不比最簡單的 c 庫函數(shù) strstr() 快多少，而 BM 算法雖然通常比 KMP 算法快，但 BM 算法也還不是現(xiàn)有字符串查找算法中最快的算法，本文最后再介紹一種比 BM 算法更快的查找算法即 Sunday 算法。

Sunday 算法由 Daniel M.Sunday 在 1990 年提出，它的思想跟 BM 算法很相似：

• 只不過 Sunday 算法是從前往后匹配，在匹配失敗時關(guān)注的是文本串中參加匹配的最末位字符的下一位字符。
  • 如果該字符沒有在模式串中出現(xiàn)則直接跳過，即移動位數(shù) = 匹配串長度 + 1；
  • 否則，其移動位數(shù) = 模式串中最右端的該字符到末尾的距離 +1。

下面舉個例子說明下 Sunday 算法。假定現(xiàn)在要在文本串"substring searching algorithm"中查找模式串"search"。

1.剛開始時，把模式串與文本串左邊對齊：

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/51.png" alt="" />

2.結(jié)果發(fā)現(xiàn)在第 2 個字符處發(fā)現(xiàn)不匹配，不匹配時關(guān)注文本串中參加匹配的最末位字符的下一位字符，即標(biāo)粗的字符 i，因為模式串 search 中并不存在 i，所以模式串直接跳過一大片，向右移動位數(shù) = 匹配串長度 + 1 = 6 + 1 = 7，從 i 之后的那個字符（即字符 n）開始下一步的匹配，如下圖：

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/52.png" alt="" />

3.結(jié)果第一個字符就不匹配，再看文本串中參加匹配的最末位字符的下一位字符，是'r'，它出現(xiàn)在模式串中的倒數(shù)第3位，于是把模式串向右移動 3 位（r 到模式串末尾的距離 + 1 = 2 + 1 =3），使兩個'r'對齊，如下：

http://wiki.jikexueyuan.com/project/kmp-algorithm/images/53.png" alt="" />

4.匹配成功。

回顧整個過程，我們只移動了兩次模式串就找到了匹配位置，緣于 Sunday 算法每一步的移動量都比較大，效率很高。完。