The Boyer–Moore–Galil String Searching Strategies Revisited
Alberto Apostolico, Raffaele Giancarlo · SIAM Journal on Computing · 1986
Based on the Boyer–Moore–Galil approach, a new algorithm is proposed which requires a number of character comparisons bounded by 2n, regardless of the number of occurrences of the pattern in the textstring. Preprocessing is only slightly more involved and still requires a time linear in the pattern size.