Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。其核心思想是：在匹配過程中，模式串發(fā)現(xiàn)不匹配時，算法能跳過盡可能多的字符以進行下一步的匹配，從而提高了匹配效率。

Sunday是一個線性字符串模式匹配算法。算法的概念如下：

Sunday算法是Daniel M.Sunday于1990年提出的一種字符串模式匹配算法。其核心思想是：在匹配過程中，模式串并不被要求一定要按從左向右進行比較還是從右向左進行比較，它在發(fā)現(xiàn)不匹配時，算法能跳過盡可能多的字符以進行下一步的匹配，從而提高了匹配效率。

記模式串為S，子串為T，長度分別為N，M。

對于T，我們做一個簡單而巧妙的預(yù)處理：記錄T中每一種字符最后出現(xiàn)的位置，將其存入一個數(shù)組中。

假設(shè)在發(fā)生不匹配時S[i]≠T[j]，1≤i≤N，1≤j≤M。設(shè)S此次第一個匹配的字符位置為L。顯然，S[L+M+1]肯定要參加下一輪的匹配，并且T至少要與S[L+M+1]匹配才有可能與整個S匹配。

這時我們就尋找T中S[L+M+1]出現(xiàn)的位置了。利用我們預(yù)處理好的數(shù)組，可以O(shè)(1)查找出那個位置u，并將其直接移動至T[u]==S[L+M+1]。特殊地，若S[L+M+1]沒有在T中出現(xiàn)，那么T不可能會與S[L+M+1]匹配，則將T的第一位直接移動到S[L+M+2]，繼續(xù)匹配。直至L+M>N時，匹配完畢。

Sunday算法思想跟BM算法很相似，在匹配失敗時關(guān)注的是文本串中參加匹配的最末位字符的下一位字符。如果該字符沒有在匹配串中出現(xiàn)則直接跳過，即移動步長= 匹配串長度+1；否則，同BM算法一樣其移動步長=匹配串中最右端的該字符到末尾的距離+1。

開源代碼為：