Galil-Giancarlo

Refinement of Colussi which performs at most $4n/3$ inspections in the worst case.

Appeared in:

• [59]: Galil, Z., Giancarlo, R.: On the exact complexity of string matching: Upper bounds. SIAM J. Comput. 21(3), 407–437 (1992), http://dx.doi.org/10.1137/0221028 ↗