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

算法步骤详解

1. 对模式串构建一个“偏移表”（shift table），记录每个字符在模式串中最右边出现的位置到末尾的距离。
2. 从主串开头开始，逐字符与模式串比较。
3. 如果完全匹配，返回匹配位置。
4. 如果不匹配，查看主串中当前窗口后一位的字符（即 pattern_len 位置的字符）：
• 若该字符不在模式串中，则跳过整个模式串长度 + 1；
• 若在，则根据偏移表跳转相应距离。

C语言实现Sunday算法

下面我们用C语言完整实现Sunday算法。代码包含偏移表构建和主匹配逻辑。

#include <stdio.h>#include <string.h>// 构建偏移表：记录每个字符到模式串末尾的最短距离void buildShiftTable(const char* pattern, int shift[256], int patternLen) {    // 初始化所有字符的偏移为 patternLen + 1    for (int i = 0; i < 256; i++) {        shift[i] = patternLen + 1;    }    // 遍历模式串，更新每个字符的偏移值（保留最右出现的位置）    for (int i = 0; i < patternLen; i++) {        shift[(unsigned char)pattern[i]] = patternLen - i;    }}// Sunday算法主函数int sundaySearch(const char* text, const char* pattern) {    int textLen = strlen(text);    int patternLen = strlen(pattern);        if (patternLen == 0) return 0;    if (textLen < patternLen) return -1;        int shift[256];    buildShiftTable(pattern, shift, patternLen);        int i = 0; // 主串当前匹配起始位置    while (i <= textLen - patternLen) {        int j = 0;        // 尝试匹配        while (j < patternLen && text[i + j] == pattern[j]) {            j++;        }        if (j == patternLen) {            return i; // 找到匹配        }                // 查看主串中当前窗口后一位的字符        if (i + patternLen < textLen) {            unsigned char nextChar = text[i + patternLen];            i += shift[nextChar];        } else {            break; // 已超出主串范围        }    }        return -1; // 未找到}// 测试函数int main() {    const char* text = "Hello, this is a Sunday algorithm example!";    const char* pattern = "Sunday";        int pos = sundaySearch(text, pattern);    if (pos != -1) {        printf("Pattern found at index: %d\n", pos);    } else {        printf("Pattern not found.\n");    }        return 0;}

算法优势与适用场景

Sunday算法在平均情况下的时间复杂度接近 O(n/m)，其中 n 是主串长度，m 是模式串长度。它的最大优点是实现简单、逻辑清晰，特别适合用于文本编辑器、搜索引擎等需要快速字符串查找的场景。

与其他算法相比，Sunday算法不需要复杂的预处理（如KMP的next数组），也不依赖模式串内部结构，仅通过一个简单的偏移表就能实现高效跳转。

总结

通过本教程，你已经掌握了如何用C语言实现Sunday字符串查找算法。无论你是初学者还是有一定经验的开发者，理解并应用这种高效字符串搜索方法都能显著提升你的程序性能。

记住，关键在于偏移表的构建和跳转逻辑。多动手写几遍代码，你就能熟练运用这项实用技能！

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