Horspool 字元串比對算法對Boyer-Moore算法的簡化算法。
Horspool 算法是一種基于字尾比對的方法，是一種“跳躍式”比對算法，具有sub-linear亞線性時間複雜度。
Horspool 算法：
對于每個搜尋視窗，該算法将視窗内的最後一個字元和模式串中的最後一個字元進行比較。如果相等，則需要進行一個校驗過程。該校驗過程在搜尋視窗中從後向前對文本和模式串進行比較，直到完全相等或者在某個字元處不比對。無論比對與否，都将根據字元d在模式串中的下一個出現位置将視窗向右移動。
可以使用下圖進行了解：
(1)視窗大小與模式串大小相同，視窗内容為文本内容的一部分。
(2)對于視窗而言，每次從後向前比對，直到全部相等(比對)，或者遇到不相等。
(3)遇到不相等時，根據視窗中最後一個字元在模式串中的位置，視窗進行移動。如果模式串中有多個相同的字元，選擇最後一個字元為準，以避免漏解。
代碼(C++)：
View Code
程式運作：