as opposed to shifting, the galil rule deals with speeding up the actual comparisons done at each alignment by skipping sections that are known to match. suppose that at an alignment , is compared with down to character of . then if is shifted to such that its left end is between and , in the next comparison phase a prefix of must match the substring . thus if the comparisons get down to position of , an occurrence of can be recorded without explicitly comparing past . in addition to increasing the efficiency of boyer-moore, the galil rule is required for proving linear-time execution in the worst case.