methods vary on the exact form the table for the bad character rule should take, but a simple constant-time lookup solution is as follows: create a 2d table which is indexed first by the index of the character in the alphabet and second by the index in the pattern. this lookup will return the occurrence of in with the next-highest index or -1 if there is no such occurrence. the proposed shift will then be , with lookup time and space, assuming a finite alphabet of length .