Horspool算法C语言实现步骤是怎样的？

Horspool 算法简介

Horspool 算法是一种用于字符串匹配的高效算法，它是 Boyer-Moore 算法的简化版本，其核心思想是从右向左比较模式串和文本串，并且在发生不匹配时，利用预处理得到的“坏字符规则”（Bad Character Rule）来向右滑动模式串，从而跳过不必要的比较。

与 Boyer-Moore 算法不同，Horspool 只关心模式串最后一个字符在文本串中的位置，而不是所有不匹配字符的位置，这使得它的预处理更简单，实现也更简洁，同时在很多实际情况下，其性能与 Boyer-Moore 算法相当。

算法核心思想

1. 预处理阶段：

   • 创建一个位移表（Shift Table），通常是一个大小为字符集大小的数组（对于 ASCII 字符，大小为 256）。
   • 对于模式串中的每一个字符（除了最后一个），计算该字符到模式串末尾的距离，并将这个值存入位移表中。
   • 对于模式串中没有出现过的字符，或者只在末尾出现过的字符，其位移值为模式串的长度 m。
   • 关键点：模式串中最后一个字符不参与构建位移表，如果它在模式串的其他位置出现，则以最右边的那个为准（但通常实现时，我们会直接覆盖）。

2. 搜索阶段：

   • 将模式串与文本串的当前对齐位置进行比较（从右向左）。
   • 如果完全匹配：则记录匹配成功的起始位置，根据位移表，将模式串向右滑动 m 位（或者更准确地说，滑动到下一个可能的起始位置），继续搜索。
   • 如果不匹配：
     • 查看文本串中与模式串最后一个字符对应位置的字符 c。
     • 在位移表中查找字符 c 对应的位移值 shift。
     • 将模式串向右滑动 shift 位。

算法示例

假设：

• 模式串 (Pattern): BANANA
• 文本串 (Text): I AM A BANANA FAN

预处理 (构建位移表): 模式串长度 m = 6，我们为 B, A, N 计算位移。

• B: 距离末尾的距离是 5。
• A: 距离末尾的距离是 1 (最右边的 A)。
• N: 距离末尾的距离是 2。

位移表（部分）: | 字符 | 位移值 | | :--- | :--- | | A | 1 | | B | 5 | | N | 2 | | 其他 | 6 |

搜索过程:

1. 初始对齐:

   
   （图片来源网络，侵删）

   Text:    I   A M   A   B A N A N A   F A N
   Pattern:         B A N A N A

   比较从右向左：A vs A -> N vs N -> A vs A -> N vs N -> A vs A -> B vs B。匹配成功！ 记录位置 9。

2. 继续搜索: 滑动模式串，我们看文本串中下一个字符 F。

   Text:    I   A M   A   B A N A N A   F A N
   Pattern:                     B A N A N A

   模式串最后一个字符是 A，与文本串中的 F 不匹配。 查找 F 的位移值：shift['F'] = 6。 将模式串向右滑动 6 位。

3. 再次对齐:

   Text:    I   A M   A   B A N A N A   F A N
   Pattern:                                 B A N A N A

   模式串已经超出文本串长度,搜索结束。

C 语言实现

下面是一个完整的、带有详细注释的 C 语言实现。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// 定义字符集大小，这里使用标准ASCII (0-255)
#define ALPHABET_SIZE 256
/**
 * @brief 构建Horspool算法的位移表
 * 
 * @param pattern 模式串
 * @param shift_table 位移表
 * @param m 模式串的长度
 */
void build_shift_table(const char *pattern, int shift_table[], int m) {
    // 1. 初始化位移表：将所有字符的初始位移值设为模式串的长度 m
    // 这表示如果一个字符在模式串中没有出现过，就一次性跳过整个模式串的长度
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        shift_table[i] = m;
    }
    // 2. 遍历模式串，更新位移表
    // 注意：这里只遍历到 m-1，即不包括最后一个字符
    for (int i = 0; i < m - 1; i++) {
        char c = pattern[i];
        // 计算该字符到模式串末尾的距离 (m - 1 - i)
        // 并存入位移表，如果同一个字符多次出现，后面的会覆盖前面的，
        // 这符合算法要求，我们取最右边的那个位置。
        shift_table[(unsigned char)c] = m - 1 - i;
    }
}
/**
 * @brief 使用Horspool算法在文本串中搜索模式串
 * 
 * @param text 文本串
 * @param pattern 模式串
 */
void horspool_search(const char *text, const char *pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    if (m == 0 || n < m) {
        printf("Pattern is empty or text is shorter than pattern.\n");
        return;
    }
    // 创建并初始化位移表
    int shift_table[ALPHABET_SIZE];
    build_shift_table(pattern, shift_table, m);
    int i = 0; // i 是文本串中当前对齐位置的索引
    int comparisons = 0; // 用于统计比较次数
    printf("Searching for \"%s\" in \"%s\"...\n", pattern, text);
    // 主循环，只要模式串还在文本串范围内就继续
    while (i <= n - m) {
        int j = m - 1; // j 是模式串中从后向前比较的索引
        // 从右向左比较字符
        while (j >= 0 && text[i + j] == pattern[j]) {
            comparisons++;
            j--;
        }
        // j < 0，说明所有字符都匹配了
        if (j < 0) {
            printf("Match found at index: %d\n", i);
            // 找到一个匹配后，继续查找下一个可能的匹配
            // 根据坏字符规则，我们看 text[i + m] 的字符（如果存在）
            // text[i + m] 不在模式串中，则移动 m 位
            // 如果在，则移动 shift_table[text[i + m]] 位
            // 这与算法逻辑一致，直接移动 shift_table[text[i + m]] 即可
            if (i + m < n) {
                i += shift_table[(unsigned char)text[i + m]];
            } else {
                i += m; // 如果到了末尾，直接移动 m 位结束
            }
        } else {
            // 如果不匹配
            comparisons++;
            // 获取文本串中与模式串最后一个字符对应位置的字符
            char bad_char = text[i + m - 1];
            // 根据位移表决定移动的距离
            i += shift_table[(unsigned char)bad_char];
        }
    }
    printf("Total comparisons made: %d\n", comparisons);
}
int main() {
    const char *text1 = "I AM A BANANA FAN";
    const char *pattern1 = "BANANA";
    horspool_search(text1, pattern1);
    // 预期输出: Match found at index: 9
    printf("\n----------------------------------------\n\n");
    const char *text2 = "ABAAABCDABCDABCDABDE";
    const char *pattern2 = "ABCDABD";
    horspool_search(text2, pattern2);
    // 预期输出: Match found at index: 11
    printf("\n----------------------------------------\n\n");
    const char *text3 = "FINDNEEDLEINAHAYSTACK";
    const char *pattern3 = "NEEDLE";
    horspool_search(text3, pattern3);
    // 预期输出: Match found at index: 4
    printf("\n----------------------------------------\n\n");
    const char *text4 = "THISISATESTSTRING";
    const char *pattern4 = "XYZ";
    horspool_search(text4, pattern4);
    // 预期输出: No match found.
    return 0;
}

代码讲解

1. build_shift_table 函数:

   • 首先初始化一个大小为 ALPHABET_SIZE (256) 的数组 shift_table，将所有值设为模式串长度 m，这是处理未知字符或只在末尾出现的字符的情况。
   • 然后遍历模式串 pattern[0] 到 pattern[m-2]（不包括最后一个字符）。
   • 对于每个字符 pattern[i]，计算它到模式串末尾的距离 m - 1 - i，并用这个值更新 shift_table 中对应的位置。
   • 使用 (unsigned char) 进行强制类型转换是为了确保 char 是负数时也能正确作为数组下标。

2. horspool_search 函数:

   • 初始化: 获取文本串和模式串的长度 n 和 m，处理边界情况（模式串为空或文本串比模式串短）。
   • 创建位移表: 调用 build_shift_table 函数。
   • 主循环 while (i <= n - m): 循环条件确保模式串不会越界。
   • 内层比较 while (j >= 0 && ...): 从模式串的末尾 (m-1) 开始，逐个字符向左比较。
   • 匹配成功 (if (j < 0)):
     • 打印匹配的起始索引 i。
     • 为了继续查找,移动模式串，移动的距离由文本串中 i+m 位置的字符决定，即 i += shift_table[text[i + m]]，这完全符合 Horspool 的滑动规则。
   • 匹配失败 (else):
     • 获取文本串中当前与模式串最后一个字符对齐的字符 text[i + m - 1]。
     • 根据这个 bad_char 从位移表中查到滑动距离，更新 i。
   • 比较次数统计: 每次进入内层 while 循环或 else 分支时，comparisons 都会加一，用于直观地展示算法的效率。

算法复杂度分析

• 预处理时间: O(m + k)，m 是模式串长度，k 是字符集大小（这里是 256），由于 k 是常数，所以可以简化为 O(m)。
• 搜索时间:
  • 最坏情况: O(m*n)，文本串是 AAAA...，模式串是 BAAA...，每次比较都会在最后一个字符失败，并且每次只滑动 1 位。
  • 平均情况: O(n)，在大多数自然语言文本中，算法表现非常出色，平均比较次数接近 n。

Horspool 算法以其简洁的实现和良好的平均性能，成为字符串匹配领域中一个非常实用的算法。