I have some doubts about the need for backward checking in the Horspool algorithm.
The shift value depends only on the last character of the current window in the text. Whether the substring comparison is done forward or backward doesn’t affect the shift itself. Backward checking might avoid an extra access to retrieve the last character, but that seems negligible.
The goal of the comparison phase is to detect mismatches as early as possible to avoid unnecessary work. However, when the window is shifted, it is shifted so that the last occurrence of the mismatching character (from the pattern, excluding its last character) aligns with that character in the text. In this context, backward checking may end up checking these two aligned characters earlier than forward checking would—possibly leading to a comparison that don’t help avoid work any better than a forward check would.
Why is backward checking truly better than forward checking in the Horspool algorithm?