  We give algorithms to accelerate the computation of deterministic finite
automata (DFA) by calculating the state of a DFA n positions ahead utilizing a
reverse scan of the next n characters. Often this requires scanning fewer than
n characters resulting in a fraction of the input being skipped and a
commensurate increase in processing speed. The skipped fraction is > 80% in
several of our examples. We introduce offsetting finite automata (OFA) to
encode the accelerated computation. OFA generalize DFA by adding an integer
offset to the current input index at each state transition. We give algorithms
for constructing an OFA that accepts the same language as a DFA while possibly
skipping input, and for matching with an OFA. Compared to previous algorithms
that attempt to skip some of the input, the new matching algorithm can skip
more often and can skip farther. In the worst case the new matching algorithm
scans the same number of characters as a simple forward scan, whereas previous
approaches often scan more, so the new algorithm can be used as a reliable
replacement for the simple forward scan. Additionally, the new algorithm adapts
to available memory and time constraints.
