Sunday算法详解（C语言高效字符串匹配实现指南）

例如，在主串 "abcxabcdabxabcdabcdabcy" 中查找模式串 "abcdabcy"，如果某次比对失败，Sunday算法会检查主串中当前窗口后一位的字符（比如 'x'），然后根据预处理表决定跳过多少位，从而减少不必要的比较。

算法步骤

1. 预处理：为模式串构建一个偏移表（shift table），记录每个字符在模式串中最右边出现的位置到末尾的距离。
2. 从主串开头开始，逐字符与模式串比对。
3. 若完全匹配，返回起始位置；若不匹配，查看主串中“当前窗口后一位”的字符。
4. 根据偏移表决定模式串向右移动的步长，继续下一轮比对。

C语言实现

下面是一个完整的Sunday算法实现代码：

#include <stdio.h>#include <string.h>#define MAX_CHAR 256  // ASCII 字符总数// 构建偏移表void buildShiftTable(char* pattern, int len, int shiftTable[]) {    // 初始化所有字符的偏移为模式长度 + 1    for (int i = 0; i < MAX_CHAR; i++) {        shiftTable[i] = len + 1;    }    // 遍历模式串，记录每个字符最右出现位置到末尾的距离    for (int i = 0; i < len; i++) {        shiftTable[(unsigned char)pattern[i]] = len - i;    }}// Sunday 算法主函数int sundaySearch(char* text, char* pattern) {    int textLen = strlen(text);    int patLen = strlen(pattern);        if (patLen == 0) return 0;    if (textLen < patLen) return -1;        int shiftTable[MAX_CHAR];    buildShiftTable(pattern, patLen, shiftTable);        int i = 0; // 主串当前比对起始位置    while (i <= textLen - patLen) {        int j = 0;        // 逐字符比对        while (j < patLen && text[i + j] == pattern[j]) {            j++;        }        if (j == patLen) {            return i; // 找到匹配        }                // 查看窗口后一位字符        if (i + patLen < textLen) {            unsigned char nextChar = text[i + patLen];            i += shiftTable[nextChar];        } else {            break; // 超出主串范围        }    }        return -1; // 未找到}// 测试函数int main() {    char text[] = "abcxabcdabxabcdabcdabcy";    char pattern[] = "abcdabcy";        int pos = sundaySearch(text, pattern);    if (pos != -1) {        printf("匹配成功！位置：%d\n", pos);    } else {        printf("未找到匹配。\n");    }        return 0;}

代码解析

• buildShiftTable 函数用于构建偏移表。对于不在模式串中的字符，偏移为 len + 1，表示可以直接跳过整个窗口。
• sundaySearch 是核心函数，使用 while 循环不断比对并跳转。
• 注意类型转换 (unsigned char)，防止负索引导致数组越界。

为什么选择Sunday算法？

相比其他高效字符串搜索算法，Sunday算法具有以下优势：

• 实现简单，逻辑清晰，适合初学者理解。
• 平均时间复杂度为 O(n)，在实际应用中往往比KMP更快。
• 预处理只需 O(m) 时间和空间（m 为模式串长度）。

总结

通过本教程，你已经掌握了如何用C语言实现Sunday算法。它是一种实用且高效的字符串匹配工具，适用于文本编辑器、搜索引擎等需要快速查找子串的场景。动手试试吧！修改测试用例，观察不同输入下的运行结果，加深理解。

关键词回顾：Sunday算法、C语言字符串匹配、高效字符串搜索算法、Sunday算法实现。