Editing Boyer–Moore string-search algorithm (section)

====Preprocessing====
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 {{mvar|c}} in the alphabet and second by the index {{mvar|i}} in the pattern. This lookup will return the occurrence of {{mvar|c}} in {{mvar|P}} with the next-highest index {{tmath|j < i}} or -1 if there is no such occurrence. The proposed shift will then be {{tmath|i - j}}, with {{tmath|O(1)}} lookup time and {{tmath|O(km)}} space, assuming a finite alphabet of length {{mvar|k}}.

The C and Java implementations below have a {{tmath|O(k)}} space complexity (make_delta1, makeCharTable). This is the same as the original delta1 and the [[Boyer–Moore–Horspool algorithm#Description|BMH bad-character table]]. This table maps a character at position {{tmath|i}} to shift by {{tmath|\operatorname{len}(p) - 1 - i}}, with the last instance—the least shift amount—taking precedence. All unused characters are set as {{tmath|\operatorname{len}(p)}} as a sentinel value.