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

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

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

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

1.剛開(kāi)始時(shí)，把模式串與文本串左邊對(duì)齊：

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

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

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

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

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

4.匹配成功。

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