Editing Boyer–Moore string-search algorithm (section)

====Preprocessing====
The good-suffix rule requires two tables: one for use in the general case (where a copy '''''{{prime|t}}''''' is found), and another for use when the general case returns no meaningful result. These tables will be designated {{mvar|L}} and {{mvar|H}} respectively. Their definitions are as follows:<ref name = "ASTS" />

<blockquote>
For each {{mvar|i}}, {{tmath|L[i]}} is the largest position less than {{mvar|m}} such that string {{tmath|P[i..m]}} matches a suffix of {{tmath|P[1..L[i]]}} and such that the character preceding that suffix is not equal to {{tmath|P[i-1]}}. {{tmath|L[i]}} is defined to be zero if there is no position satisfying the condition.
</blockquote>

<blockquote>
Let {{tmath|H[i]}} denote the length of the largest suffix of {{tmath|P[i..m]}} that is also a prefix of {{mvar|P}}, if one exists. If none exists, let {{tmath|H[i]}} be zero.
</blockquote>

Both of these tables are constructible in {{tmath|O(m)}} time and use {{tmath|O(m)}} space. The alignment shift for index {{mvar|i}} in {{mvar|P}} is given by {{tmath|m - L[i]}} or {{tmath|m - H[i]}}. {{mvar|H}} should only be used if {{tmath|L[i]}} is zero or a match has been found.


-----------------------------------------------