The Bad Character Shift Rule

The Bad Character Shift Rule allows the pattern to be shifted by multiple characters upon a mismatch, rather than one character, as in the naive approach.

Understanding The Bad Character Shift Rule

When scanning a pattern[1...m] from right-to-left against a text[1...n] and a mismatch occurs at some position $k$ in the pattern, i.e. pat[k] != txt[j+k-1].

Then the bad character is defined as the mismatched character in the text, i.e. bad_character = txt[j+k-1].

The pattern is moved so that the bad_character in the text aligns with its rightmost occurrence (to the left of the point of mismatch) in the pattern. To efficiently determine the shift amount, a Rightmost Occurrence Table is utilised.

Rightmost Occurrence Table

The Rightmost Occurrence Table is a precomputed table $R_k(x)$ for all possible characters in the pattern that stores the rightmost occurrence of x to the left of $k$ in the pattern. If no such occurrence exists, $R_k(x)=0$

$$R_k(x)=\{\begin{array}{ll}\text{Position of the rightmost occurrence of x to the left of k in the pattern}& \text{if x occurs to the left of k in the pattern}\\ 0& \text{otherwise}\end{array}$$

This table can be used to determine how far to shift the pattern when a mismatch occurs.

Note that "the left of $k$" is exclusive, so not including pat[k]

Example of a Rightmost Occurrence table

For the pattern, pat[1...7] = tbapxab, then the corresponding $R_k(x)$ is computed as so:

• For $R_1$:
  • There are no characters to the left of $k=1$, thus consider this the base case and default all $R_1$ values to $0$
• For $R_2$:
  • The only character to the left of $k=2$ is t at position 1.
  • Thus, $R_2(t)=1$, and all other values remain $0$.
• For $R_3$:
  • The characters to the left of $k=3$ are t at position 1 and b at position 2.
  • $R_3(t)=1$, $R_3(b)=2$, and all other values remain $0$.
• For $R_4$:
  • The characters to the left of $k=4$ are t at 1, b at 2, and a at 3.
  • $R_4(t)=1$, $R_4(b)=2$, $R_4(a)=3$, and all others remain $0$.
• For $R_5$:
  • The characters to the left of $k=5$ are t at 1, b at 2, a at 3, and p at 4.
  • $R_5(t)=1$, $R_5(b)=2$, $R_5(a)=3$, $R_5(p)=4$, and others remain $0$.
• For $R_6$:
  • The characters to the left of $k=6$ are t at 1, b at 2, a at 3, p at 4, and x at 5.
  • $R_6(t)=1$, $R_6(b)=2$, $R_6(a)=3$, $R_6(p)=4$, $R_6(x)=5$, and others remain $0$.
• For $R_7$:
  • The characters to the left of $k=7$ are t at 1, b at 2, a at 3, p at 4, x at 5, and a at 6.
  • Since a appears at both 3 and 6, we take the rightmost occurrence before 7, which is 6.
  • $R_7(t)=1$, $R_7(b)=2$, $R_7(a)=6$, $R_7(p)=4$, $R_7(x)=5$, and others remain $0$.

This results in a final table:

	a	b	p	t	x	z
$R_1(\cdot )$	0	0	0	0	0	0
$R_2(\cdot )$	0	0	0	1	0	0
$R_3(\cdot )$	0	2	0	1	0	0
$R_4(\cdot )$	3	2	0	1	0	0
$R_5(\cdot )$	3	2	4	1	0	0
$R_6(\cdot )$	3	2	4	1	5	0
$R_7(\cdot )$	6	2	4	1	5	0

Note that all $R_k(z)$ values are $0$ since z does not appear in the string. Although no other characters are shown, in practice, this table is precomputed for the entire alphabet and ordered by character value, which is why z is highlighted.

Computing $R_k$

Let text[1...n] and pat[1...m] be strings from the alphabet $\Sigma$.

To efficiently compute $R_k$ , pre-process pat and store, for each character $x\in \Sigma$, and index $k\in [\mathrm{1...}m]$, the rightmost occurrence of x to the left of $k$ in the pattern.

To achieve this, the algorithm iterates over the pattern whilst keeping track of the last seen index of each character.

def compute_rightmost_occurrence_table(pattern: str, alphabet: set) -> list[dict]:
    m = len(pattern)
    R = []
    # Tracks the last seen index of each character, defaults to -1. 
    last_seen = {char: -1 for char in alphabet}     
    # Base Case: R_0 is always 0, as there is nothing to the left of index 0
    R.append(last_seen.copy())
    # Iterates from 1 to m
    for k in range(1, m):
        # Get the character at position k-1 (to the left of k)
        char = pattern[k-1]  
        # Update the last seen position of the character
        last_seen[char] = k - 1
        # Copy the updated last_seen mapping into R_k
        R.append(last_seen.copy())
    return R

At the end of computation, the last_seen dictionary is actually the $R$ value for the Simple Bad Character Shift Rule

Time Complexity Analysis

• The last_seen dictionary (as well as $R_0$) is initialised in $O(\Sigma )$ time
• The main loop iterates $m$ times and includes:
  • Dictionary lookup and updates which is amortised $O(1)$ and worst case $O(\Sigma )$ due to hash collisions
  • Copying the last_seen dictionary, which is $O(\Sigma )$ time.
• The total complexity is thus $O(m\ast \Sigma )$ in the worst case, however, note that the alphabet is often a constant.
• Additionally, an ASCII dictionary can be used to ensure no hash collisions and $O(1)$ lookup and update.

Space Complexity Analysis

• The last_seen dictionary has $O(\Sigma )$ complexity.
• The $R_k$ table is of size $m$, where each entry is a dictionary of size $\Sigma$ resulting in $O(m\times \Sigma )$ space.
• The total complexity is thus $O(m\times \Sigma )$, however, note that the alphabet is often a constant.

Implementing The Bad Character Shift Rule

Consider a general iteration where pat[1...m] is aligned with text[j...j+m-1] and a right-to-left scan is performed. If a mismatch occurs at some position $k$ in pat, then the bad character—text[j+k-1], must align with its rightmost occurrence in pat (to the left of $k$).

To determine the shift amount, we use the pre-computed Rightmost Occurrence Table $R_k(x)$:

$\text{shift}=k-R_k(x)$

When $R_k(x)=0$, then the shift amount is $k$. This makes sense because if the character doesn’t appear in the pattern, a match is impossible, so we can safely shift the entire pattern past it.

This is actually known as the Extended Bad Character Shift Rule. The regular rule uses $R(x)$, which only considers the rightmost occurrence of $x$ in the pattern without respect to $k$

The regular rule benefits over the extended rule in space efficiency, as the space complexity is reduced to $O(\Sigma )$ due to the only data being stored is the last_seen dictionary ($O(\Sigma$).

However, it is less time efficient in the case where $R(x)>k$ (which can’t happen in the extended rule), because there’s no appropriate shift, so a naive 1-character shift must be made.

Example of the Bad Character Shift Rule (Three Cases)

Case 1: Bad Character Appears in the Pattern

• The pattern and text are compared right-to-left until a mismatch is found at txt[5] = T with pat[3] = A.
  • The bad character is txt[5] = T.
• We look for the rightmost occurrence of T in the pattern to the left of index $3$.
  • The rightmost occurrence is pat[1] = T.
• The pattern is shifted so that pat[1] = T aligns with txt[5] = T.
  • The shift amount is calculated as 3 - 1 = 2.

Case 2: Multiple Occurrences of Bad Character in the Pattern

• A mismatch occurs at txt[9] = B with pat[5] = X.
  • The bad character is txt[9] = B.
• B appears twice in the pattern: at pat[4] = B and pat[7] = B.
  • We choose the rightmost occurrence before index $5$, which is pat[4] = B.
• The pattern is shifted so that pat[4] = B aligns with txt[9] = B.
  • The shift amount is 5 - 4 = 1.

Case 3: Bad Character Not in the Pattern

• A mismatch occurs at txt[12] = J with pat[7] = B.
  • The bad character is txt[12] = J.
• J does not appear in the pattern.
  • Since J is absent, the pattern is fully shifted past it.
  • The shift amount is 7 - 0 = 7.