Horspool算法C语言实现步骤是怎样的？-C语言-盈思创科技

Horspool 算法简介

Horspool 算法的核心思想是利用模式串中出现的字符信息，在匹配失败时进行“跳跃”，从而跳过大量不必要的比较，提高效率。

（图片来源网络，侵删）

工作原理：

预处理阶段：创建一个“跳跃表”（Shift Table），也称为“坏字符表”，这个表记录了模式串中的每个字符，在匹配失败时，模式串应该向右移动多少位。
- 对于模式串 P 中的每一个字符 c，计算其跳跃距离 shift[c]。
- 规则：shift[c] = (m - 1 - i)，m 是模式串的长度，i 是字符 c 在模式串中从右向左第一次出现的位置，如果字符 c 不在模式串中，则 shift[c] = m。
搜索阶段：
- 将模式串 P 与文本串 T 的开头对齐。
- 从右向左逐个比较模式串和文本串的字符。
- 匹配成功
  - 如果所有字符都匹配,则找到一个匹配位置。
  - 然后根据跳跃表,将模式串向右移动 shift[T[k + m - 1]] 位（k 是当前模式串的起始位置），继续搜索下一个可能的匹配。
- 匹配失败
  - 在比较过程中,如果发现不匹配的字符 T[k + j]（j 是当前比较的位置，从 m-1 开始递减）。
  - 查看坏字符表 shift[T[k + m - 1]]（注意，这里看的是当前对齐位置的模式串最后一个字符对应的文本字符）。
  - 将模式串向右移动 shift[T[k + m - 1]] 位。

举个例子：

模式串 P = "BARBER" (m = 6) 文本串 T = "JIM_SAW_ME_IN_A_BARBER_SHOP"

预处理： 创建跳跃表

（图片来源网络，侵删）

m-1 = 5
shift['B'] = 5 - 0 = 5 (B在索引0)
shift['A'] = 5 - 1 = 4 (A在索引1)
shift['R'] = 5 - 2 = 3 (R在索引2)
shift['E'] = 5 - 3 = 2 (E在索引3)
shift[' '] = 5 - 4 = 1 (空格在索引4)
对于其他所有字符（如 'J', 'I', 'M', 'S', 'O', 'H', 'P'等），shift[c] = m = 6。

跳跃表 shift 大致如下： | ' ' | 'A' | 'B' | 'E' | 'R' | 其他 | |:---:|:---:|:---:|:---:|:---:|:----:| | 1 | 4 | 5 | 2 | 3 | 6 |

搜索过程：

初始对齐：
```
T: JIM_SAW_ME_IN_A_BARBER_SHOP
P: BARBER
```
比较最后一个字符：T[5]('E') vs P[5]('R')，不匹配！坏字符是 T[5] = 'E'，查表 shift['E'] = 2。向右移动 2 位。
（图片来源网络，侵删）
第一次移动后：
```
T: JIM_SAW_ME_IN_A_BARBER_SHOP
P:   BARBER
```
比较最后一个字符：T[7]('M') vs P[5]('R')，不匹配！坏字符是 T[7] = 'M'，查表 shift['M'] = 6。向右移动 6 位。
第二次移动后：
```
T: JIM_SAW_ME_IN_A_BARBER_SHOP
P:         BARBER
```
比较最后一个字符：T[13]('R') vs P[5]('R')，匹配！继续向左比较：T[12]('A') vs P[4]('E')，不匹配！坏字符是 T[13] = 'R'，查表 shift['R'] = 3。向右移动 3 位。
第三次移动后：
```
T: JIM_SAW_ME_IN_A_BARBER_SHOP
P:            BARBER
```
比较最后一个字符：T[19]('R') vs P[5]('R')，匹配！继续向左比较：T[18]('A') vs P[4]('E')，不匹配！坏字符是 T[19] = 'R'，查表 shift['R'] = 3。向右移动 3 位。
第四次移动后：
```
T: JIM_SAW_ME_IN_A_BARBER_SHOP
P:                  BARBER
```
比较最后一个字符：T[25]('P') vs P[5]('R')，不匹配！坏字符是 T[25] = 'P'，查表 shift['P'] = 6。向右移动 6 位，模式串超出文本范围，搜索结束。

C 语言实现

下面是 Horspool 算法的完整 C 语言实现。

#include <stdio.h>
#include <string.h>
#include <stdlib.h> // 用于 exit 函数
// 定义字符集的大小，ASCII 字符集
#define ALPHABET_SIZE 256
/**
 * @brief 预处理阶段，构建 Horspool 跳跃表
 * @param pattern 模式串
 * @param shift 跳跃表数组
 * @param m 模式串的长度
 */
void precomputeShifts(const char* pattern, int shift[], int m) {
    // 1. 初始化跳跃表：将所有字符的默认跳跃值设为模式串的长度 m
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        shift[i] = m;
    }
    // 2. 根据模式串填充跳跃表
    // 注意：我们只遍历模式串的前 m-1 个字符
    // 因为最后一个字符的跳跃值不会被用到（匹配成功时会用其他规则处理）
    for (int i = 0; i < m - 1; i++) {
        char c = pattern[i];
        // 跳跃距离 = 模式串长度 - 1 - 字符 c 的位置
        // 这样，当遇到字符 c 时，模式串会移动到 c 的正下方
        shift[(unsigned char)c] = m - 1 - i;
    }
}
/**
 * @brief Horspool 字符串搜索算法
 * @param text 文本串
 * @param pattern 模式串
 */
void horspoolSearch(const char* text, const char* pattern) {
    int n = strlen(text);    // 文本串长度
    int m = strlen(pattern); // 模式串长度
    // 如果模式串比文本串还长，直接返回
    if (m > n) {
        printf("Pattern not found.\n");
        return;
    }
    int shift[ALPHABET_SIZE]; // 创建跳跃表
    // 预处理阶段
    precomputeShifts(pattern, shift, m);
    int k = 0; // k 是当前模式串在文本串中的对齐起始位置
    int found = 0; // 标记是否找到匹配
    // 搜索阶段
    // 循环条件：k + m <= n，确保模式串不会超出文本串范围
    while (k <= n - m) {
        int j = m - 1; // 从模式串的最后一个字符开始比较
        // 从右向左逐个字符比较
        while (j >= 0 && pattern[j] == text[k + j]) {
            j--;
        }
        // j < 0，说明所有字符都匹配了
        if (j < 0) {
            printf("Pattern found at index: %d\n", k);
            found = 1;
            // 找到一个匹配后，继续向右搜索下一个可能的匹配
            // 这里我们移动 1 位，也可以根据模式串本身的特性设计更复杂的移动规则
            // Horspool 的原始算法在找到匹配后，会移动 shift[text[k + m - 1]] 位
            // 但为了简单起见，我们移动 1 位。
            k += (k + m < n) ? shift[(unsigned char)text[k + m]] : 1;
        } else {
            // 如果不匹配，根据坏字符表进行跳跃
            // 坏字符是 text[k + m - 1]
            // 跳跃距离为 shift[该字符]
            k += shift[(unsigned char)text[k + m - 1]];
        }
    }
    if (!found) {
        printf("Pattern not found.\n");
    }
}
int main() {
    char text[] = "JIM_SAW_ME_IN_A_BARBER_SHOP";
    char pattern[] = "BARBER";
    printf("Text: %s\n", text);
    printf("Pattern: %s\n\n", pattern);
    horspoolSearch(text, pattern);
    // 另一个测试用例
    printf("\n--- Another Test Case ---\n");
    char text2[] = "ABAAABCDABCDABCEABCDABCEABCD";
    char pattern2[] = "ABCEABCD";
    printf("Text: %s\n", text2);
    printf("Pattern: %s\n\n", pattern2);
    horspoolSearch(text2, pattern2);
    return 0;
}

代码解释

#define ALPHABET_SIZE 256: 定义了我们处理的字符集大小，对于标准的 ASCII 字符，256 是一个合适的值，如果只处理小写字母，可以改为 26。
precomputeShifts 函数:
- 初始化: for (int i = 0; i < ALPHABET_SIZE; i++) { shift[i] = m; }，这是关键一步，它将所有未在模式串中出现的字符的跳跃值设为 m，这意味着如果遇到一个完全无关的字符，模式串会直接跳过整个长度，效率很高。
- 填充表: for (int i = 0; i < m - 1; i++) { ... }，我们遍历模式串（除了最后一个字符），对于每个字符 pattern[i]，计算其跳跃距离 m - 1 - i，并更新到跳跃表中。shift[(unsigned char)c] 的写法是为了确保 c 是一个有效的数组索引，避免负值导致未定义行为。
horspoolSearch 函数:
- k: 当前模式串在文本串中的起始对齐位置。
- 外层 while (k <= n - m): 控制搜索过程，只要模式串还能完全放在文本串中，就继续搜索。
- 内层 while (j >= 0 && ...): 从右向左进行字符比较。j 从 m-1 开始递减，只要字符匹配，j 就减一。
- if (j < 0): j 变成负数，说明 while 循环因为 pattern[j] == text[k + j] 条件失败而退出，这意味着前面的所有字符都匹配了，即找到了一个完整匹配。
  - 打印匹配位置 k。
  - 处理找到匹配后的移动: 这是一个细节点，找到匹配后，我们通常会继续向右搜索，Horspool 算法的标准做法是使用下一个字符（text[k + m]）来决定跳跃距离。k + m 超出文本范围，则移动 1 位以避免越界。
- else: 如果没有找到匹配 (j >= 0)。
  - 获取坏字符 text[k + m - 1]。
  - 从跳跃表中获取跳跃距离 shift[bad_char]。
  - 更新对齐位置 k += shift[bad_char]，这是算法高效的核心。

算法分析

时间复杂度:
- 预处理: O(m + ALPHABET_SIZE)，m 是模式串长度，由于 ALPHABET_SIZE 是一个常数（如256），所以预处理时间是 O(m)。
- 搜索: 平均情况下为 O(n)，最坏情况下为 O(n*m)，最坏情况例如，模式串是 AAAAA，文本串是 AAAAAAAAAB，每次比较最后一个字符都失败，但坏字符表给出的跳跃距离总是 1，导致算法退化为朴素的字符串匹配。
空间复杂度: O(ALPHABET_SIZE)，用于存储跳跃表，同样，ALPHABET_SIZE 是常数，所以空间复杂度是 O(1)。

Horspool 算法实现简单，在大多数实际应用中（尤其是模式串中字符分布较均匀时）表现优异，是一种非常实用的字符串匹配算法。

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