Suppose that the pattern is p1…pm. Charge 2 tokens for each step.
Suppose that a particular step successfully matches a character. We require it to use one token to cover the cost of the successful character comparison and to put one token in the bank. We will ensure that, when the i-th pattern character is being compared to a text character, there are always i − 1 tokens in the bank.
Some steps do more than one comparison against the same text character. Each mismatch decreases the pattern index i being tested by at least 1. If a mismatch decreases the pattern index by k, we take k (≥ 1) from the bank to pay for that unsuccessful comparison, and give k−1 tokens to charity. The mismatch decreases i by k, and also decreases the number of tokens in the bank by k, so there are still the required number of tokens in the bank.
We have paid for all mismatches and all matches, except for one special case. When comparing p1, there are no tokens in the bank. If that is a mismatch, then we use the token that would have paid for a character match to pay for that mismatch. (The pattern index remains 1, and the text index increases by 1.)
If there are n text characters then there can only be n total combined matches and special mismatches, since each of those increases the text index by 1, and the text index never decreases. So the total number of character comparisons is at most 2n.