Editing Boyer–Moore string-search algorithm (section)

===The bad-character rule===

====Description====
{{float begin|side=right|width=340px}}
| -||-||-||-||X||-||-||K||-||-||-
|-
| A||N||P||A||<span style="color:#FF0000">N</span>||M||A||N||A||M||-
|-
| -||N||<span style="color:#0000FF">N</span>||A||A||M||A||N||-||-||-
|-
| -||-||-||N||<span style="color:#0000FF">N</span>||A||A||M||A||N||-
{{float end|Demonstration of bad-character rule with pattern '''P''' {{=}} '''NNAAMAN'''. There is a mismatch between '''N''' (in the input text) and '''A''' (in the pattern) in the column marked with an '''X'''. The pattern is shifted right (in this case by 2) so that the next occurrence of the character '''N''' (in the pattern '''P''') to the left of the current character (which is the middle '''A''') is found.}}

The bad-character rule considers the character in {{mvar|T}} at which the comparison process failed (assuming such a failure occurred). The next occurrence of that character to the left in {{mvar|P}} is found, and a shift which brings that occurrence in line with the mismatched occurrence in {{mvar|T}} is proposed. If the mismatched character does not occur to the left in {{mvar|P}}, a shift is proposed that moves the entirety of {{mvar|P}} past the point of mismatch.

====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.