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

为什么选择Sunday算法？

Sunday算法属于高效字符串搜索算法的一种，具有以下优势：

• 平均时间复杂度接近 O(n/m)，其中 n 是主串长度，m 是模式串长度；
• 最坏情况时间复杂度为 O(n×m)，但在实际文本中很少出现；
• 实现逻辑简单，代码可读性强，非常适合初学者学习；
• 预处理只需构建一个偏移表（shift table），空间开销小。

Sunday算法核心思想

假设我们正在主串 text 中查找模式串 pattern。算法从左到右对齐模式串，并逐字符比较：

1. 如果所有字符都匹配，则找到结果；
2. 如果不匹配，则查看主串中当前窗口右侧第一个字符（即 text[i + m]，其中 i 是当前窗口起始位置，m 是模式串长度）；
3. 根据该字符在模式串中的最右出现位置，决定模式串向右滑动的距离；
4. 若该字符不在模式串中，则直接跳过整个窗口（滑动 m+1 位）。

C++实现Sunday算法

下面是一个完整的、适合小白理解的Sunday算法实现代码：

#include <iostream>#include <vector>#include <unordered_map>#include <string>using namespace std;int sundaySearch(const string& text, const string& pattern) {    if (pattern.empty()) return 0;    int n = text.size();    int m = pattern.size();    // 构建偏移表：记录每个字符在pattern中最右边的位置    unordered_map<char, int> shift;    for (int i = 0; i < m; ++i) {        shift[pattern[i]] = m - i; // 距离末尾的距离    }    int i = 0;    while (i <= n - m) {        bool match = true;        // 逐字符比较        for (int j = 0; j < m; ++j) {            if (text[i + j] != pattern[j]) {                match = false;                break;            }        }        if (match) {            return i; // 找到匹配位置        }        // 查看text[i + m]处的字符        if (i + m < n) {            char nextChar = text[i + m];            if (shift.count(nextChar)) {                i += shift[nextChar];            } else {                i += m + 1;            }        } else {            break;        }    }    return -1; // 未找到}int main() {    string text = "hello world, this is sunday algorithm example";    string pattern = "sunday";    int pos = sundaySearch(text, pattern);    if (pos != -1) {        cout << "Pattern found at index: " << pos << endl;    } else {        cout << "Pattern not found." << endl;    }    return 0;}

代码解析

上述代码包含以下几个关键部分：

• 偏移表构建：使用 unordered_map 存储每个字符到其在模式串中最右位置的距离（从末尾算起）；
• 主循环：每次尝试匹配，失败后根据 text[i + m] 决定跳转步长；
• 边界处理：确保不会越界访问主串。

总结

Sunday算法是一种实用且高效的字符串匹配技术，特别适合需要快速实现文本搜索功能的场景。通过本教程，即使是编程新手也能掌握其基本原理和C++语言Sunday算法实现方法。建议读者动手运行代码，修改测试用例，加深理解。

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