Horspool's Algorithm

Problem Statement

Horspool's algorithm solves the String Matching problem.

Design and Strategy

Horspool's algorithm is a space-time tradeoff algorithm designed to efficiently find occurrences of a pattern \(P\) of length \(m\) within a larger text \(T\) of length \(n\). Unlike simpler algorithms that compare each character repeatedly, Horspool minimizes the total number of character comparisons by intelligently skipping portions of the text where matches cannot possibly occur.

Horspool compares characters starting from the rightmost character of the pattern moving leftward. This end-to-start comparison is strategic: mismatches near the end of the pattern are more informative, as they often justify larger shifts that skip irrelevant text. The shift distance depends only on the character aligned with the last position of the pattern in the current alignment, regardless of whether any earlier characters matched.

To illustrate, suppose we want to find the pattern "RODEO" in the text "NOW WE RODE ON HORSES". Here we have \(m=5\) and \(n=21\). We explore three scenarios based on the character in the text aligned with the last character of the pattern:

• Case 1: The aligned character does not appear in the pattern.
  Suppose the alignment places the last character of "RODEO" over a W character of the text:
  

  NOW WE RODE ON HORSES RODEO

  Since W does not appear in "RODEO", shifting fewer than \(m\) (in this case, 5) ensures that the W will not match any character in the pattern. Thus, we might as well shift by \(m\). In this case, we store \(m\) in the shift table for W. This is the case for any character not appearing in the pattern.
• Case 2: The aligned character appears somewhere in the pattern before the last position (and may or may not appear in the last position).
  Suppose the alignment places the last character of "RODEO" over an R character of the text:
  

  NOW WE RODE ON RODEO

  The R appears at index 0 of the pattern. Notice that if we shift the pattern any fewer than 4 spots, the R of the text cannot possible match anything in the pattern. In this case we store 4 in the shift table for the letter R. In general, for characters whose last appearance in the pattern is at index \(i\), where \(i \lt m-1\), the shift table value is \(m - 1 - i\). This ensures that the given occurrence of the letter in the text is aligned with its last appearance in the pattern.
• Case 3: The aligned character only occurs as the final character of the pattern.
  (Notice that if it also occurs elsewhere, it is in Case 2). For instance, if we replace the pattern "RODEO" with "RADEO", and have a situation such as the following:

  NOW WE RODE ON RADEO

  It is not hard to see that this is identical to Case 1. So we store \(m\) in the shift table for O in this case. Luckily, this is not actually a special case because, as we will see, the algorithm automatically handles it.

In summary:

Two important points to re-emphasize: First, we look at the character in the text, not the pattern. Second, we look at the character in the text that is aligned with the last character of the pattern regardless of whether or not any characters matched. So it is always the character in the text that is lined up with the last character in the pattern.

These examples/observations are the idea behind the Bad Character Heuristic. The heuristic builds a shift table that precomputes optimal shifts for each character, leading to significant reductions in unnecessary comparisons.

More concretely, given a pattern \(P\) of length \(m\), the preprocessing step to compute the shift table (also know as the bad character table) is as follows.

1. Create a shift table \(S\) that stores a shift value for each character in the alphabet.
2. Set \(S[c] = m\) for all characters \(c\) that occur in the text. This default value corresponds to shifting past the entire pattern length, assuming the character does not appear in the pattern or only appears as the final character.
3. Next, refine the shift table: For each character in the pattern from first to second-to-last (left to right), set \[S[P[j]] = m - 1 - j.\] The order is crucial; processing from left to right ensures that if a character appears multiple times, the shift value from its rightmost occurrence is retained, which guarantees the correct number of positions to shift when a mismatch occurs.

For simplicity, in most the remainder of our discussion we will assume the characters are ASCII so we can treat them as integers 0 through 255, making it easy to implement a lookup table. Many languages, including Java and C++, make this easy to do. This means we will need a shift table with 256 entries. Given that, we can write the preprocessing step of the algorithm in formal pseudocode as follows:

int [] computeShiftTable(int P[])
    m=P.length
    int[] S = new int[256];            // Create an array of size 256
    for (int i = 0; i < 256 ; i++) {   // Initialize all entries to m
        S[i] = m;
    }
    for (int j = 0; j < m - 1 ; j++) { // Update entries based on the pattern
        S[P[j]] = m - 1 - j;
    }
    return S

Let's see a few examples of constructing the table. For simplicity, the following demo restricts the characters to upper case alphabetic characters and only shows that portion of the shift table. Run it with strings like "HORSPOOL", "SHOELACES", and "CGTAATAAGTC".

If the characters in question are not ASCII, we can simply replace an array with a dictionary, which languages like Python make very easy, can be done with a HashMap in Java, or with a std::map in C++. In this case, the dictionary only needs to store entries whose values are not the full length of the pattern (\(m\)), and if a character is not in the dictionary the value is assumed to be \(m\). This means no initialization is required, and less space is used most of the time.

Now that we have a shift table, we can get into the main part of the algorithm.

1. Begin by aligning the pattern \(P\) with the start of the text \(T\).
2. Character comparisons are performed from right to left, meaning the algorithm first compares the last character of the pattern to the corresponding aligned character in the text.
1. If all characters match, record or return the starting index of this occurrence.
2. If a mismatch occurs anywhere within the pattern, lookup \(k=S[c]\), where \(c\) is the character in the text aligned with the last character of \(P\).
3. Shift the pattern to the right by \(k\) places.
4. As long as the pattern does no go past the end of the text, go back to step 2. Otherwise quit.

horspoolSearch(int[]P, int[] T, int[] S) 
    int n=T.length
    int m=P.length
    int i = 0;          // Line up P at the start of T
    while (i ≤ n - m)   // As long as pattern does not go past the end of text
        int j = m - 1;                        // Start at the end of the pattern
        while (j ≥ 0 && P[j] == T[i + j])     // As long as the characters match
            j--;                              // go to the previous character
        
        if (j < 0)               // If we made it through the whole pattern
            print(i)             // print the starting index of the match location
            
        int next = T[i + m - 1];  // Get character of text lined up with the last 
                                  // character of pattern (treated like an integer)
        i += S[next];             // Shift according to the bad character table        
        

Use this demo with several patterns and texts until you are comfortable with how the algorithm works. This demo only shows the portion of the table with characters from the pattern. The * entry indicates all other characters, which is why its value is \(m\). Do not make the text too long unless you have a wide enough monitor!

Code Implementations

In the following implementations, we assume the characters in the char arrays are ASCII characters. If they are not, the algorithms will crash (index-out-of-bounds errors). Note that for C++ we need to cast the char into unsigned char since wether or not a char is signed or unsigned is implementation dependent, and negative values would definitly cause problems. This complication can be avoided by using a dictionary/map instead of an array (but depending on your background, you may or may not know how to do that in C++, so we do not assume). Also notice that, as usual, we need to pass in the sizes of the array in C++. In the first Python implementation, we try to keep the implementation as similar to Java and C++ as possible. In it we use the ord method to convert a character to its ASCII value. We give a second version that takes advantage of the fact that dictionaries are very simple to use in Python, as well as a few other Python-shortcuts.

void horspoolSearch(char[] P, char[] T) {
    int m = P.length;
    int n = T.length;

    int[] S = new int[256];
    for (int i = 0; i < 256; i++) {
        S[i] = m;
    }
    for (int j = 0; j < m - 1; j++) {
        S[P[j]] = m - 1 - j;  // Implicit cast from char to int
    }

    int i = 0;
    while (i <= n - m) {
        int j = m - 1;
        while (j >= 0 && P[j] == T[i + j]) {
            j--;
        }
        if (j < 0) {
            System.out.println(i);
        }
        char next = T[i + m - 1];
        i += S[next];  // next implicitly cast to int
    }
}

void horspoolSearch(char P[], int m, char T[], int n) {
    int S[256];
    for (int i = 0; i < 256; i++)
        S[i] = m;

    for (int j = 0; j < m - 1; j++)
        S[(unsigned char)P[j]] = m - 1 - j;

    int i = 0;
    while (i <= n - m) {
        int j = m - 1;
        while (j >= 0 && P[j] == T[i + j])
            j--;

        if (j < 0)
            std::cout << i << std::endl;

        char next = T[i + m - 1];
        i += S[(unsigned char)next];
    }
}

def horspool_search(P, T):
    m = len(P)
    n = len(T)

    # Step 1: Build the shift table
    S = [m] * 256
    for j in range(m - 1):
        S[ord(P[j])] = m - 1 - j

    # Step 2: Search
    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and P[j] == T[i + j]:
            j -= 1
        if j < 0:
            print(i)
        i += S[ord(T[i + m - 1])]

def horspool_search(P, T):
    m = len(P)
    n = len(T)

    # Step 1: Build the shift table using a dict
    shift = {c: m for c in set(T)}  # default to m for all seen text chars
    for j in range(m - 1):
        shift[P[j]] = m - 1 - j

    # Step 2: Search
    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and P[j] == T[i + j]:
            j -= 1
        if j < 0:
            print(i)
        c = T[i + m - 1]
        i += shift.get(c, m)  # default to m if char not in shift table

Time/Space Analysis

Time Complexity: The preprocessing phase takes \(O(m + \sigma)\) time, where \(m\) is the length of the pattern and \(\sigma\) is the size of the alphabet. The \(O(\sigma)\) term accounts for initializing the shift table, and the \(O(m)\) term comes from updating the table entries based on the pattern.

In the worst case, each shift results in only a single-character shift with up to \(m\) comparisons, leading to a total time of \(O(mn)\). This can occur in contrived inputs where mismatches happen only at the end of each alignment (e.g., text is a repeated prefix of the pattern).

However, the average-case complexity is \(O(n)\) for typical inputs, especially when the alphabet is reasonably large and the pattern is not highly repetitive. This is because most mismatches are detected quickly (often near the end of the pattern), and the algorithm often shifts by several characters at once. On average, the number of character comparisons per alignment is small and independent of the pattern length, resulting in linear-time behavior for most inputs. This behavior makes Horspool’s algorithm significantly faster in practice than brute-force search, especially when the pattern is long or the character distribution is uniform.

Space Complexity: The shift table requires \(O(\sigma)\) space, which is constant for fixed-size alphabets such as ASCII (256 characters).

Variations/Improvements

Horspool's algorithm is a simplified version of the more general Boyer-Moore algorithm, which uses both the bad character rule (as in Horspool) and an additional good suffix rule to determine shift distances. While Horspool is easier to implement and performs well in practice, especially for longer patterns and larger alphabets, Boyer-Moore typically achieves better performance by using more information from partial matches. Further refinements, such as the Boyer-Moore-Horspool-Sunday algorithm, adjust the shift logic to examine characters beyond the current window, often improving average-case behavior. Other extensions and hybrid approaches balance preprocessing time and shift table complexity to optimize for specific contexts, such as small alphabets or frequent partial matches in the text.

Links to Resources

• Boyer–Moore-Horspool algorithm (Wikipedia) Overview of Horspool's algorithm.