Apostolico-Giancarlo

Variant of Boyer-Moore. It works in $O(n)$-time complexity and performs $3n/2$ comparisons in the worst case.

Appeared in:

• [7]: Apostolico, A., Giancarlo, R.: The boyer-moore-galil string searching strategies revisited. SIAM J. Comput. 15(1), 98–105 (1986), http://dx.doi.org/10.1137/0215007 ↗